题目链接：?id=2502题目大意：第一行给出起点和终点坐标，然后每一行是一个地铁线，用坐标表示，以-1 -1表示该条线路输入完毕，注意单位是米！每条线路都是直线双向，地铁时速40km/h，人步行速度10km/h，地铁只能在相邻两站间行使，，不能直接从第i站到第i+2站，若该人一到地铁站就有地铁坐，问其从起点到终点的最少需要几分钟题目分析：此题的输入建图比较麻烦，每条地铁线我们要单独处理，笛卡尔距离 / 地铁速(40km/h)作为边权，处理完每条线，再处理其他点之间的边权，笛卡儿距离 / 人速(10km/h)，然后就是裸的最短路问题，用Dijkstra求解，注意3个问题，第1：单位的换算，第2：结果要求四舍五入，第3：无穷大设置为double型！#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;int const MAX = 405;int const INF = 100000000.0;struct Node{double u, v;}nd[MAX];double dis[MAX], e[MAX][MAX];bool vis[MAX];int cnt;double get_dis(double x1, double y1, double x2, double y2){return sqrt((x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2));}void Dijkstra(int v0){for(int i = 0; i < cnt; i++)dis[i] = e[v0][i];dis[v0] = 0;vis[v0] = true;for(int i = 0; i < cnt – 1; i++){double mi = INF;int u = v0;for(int j = 0; j < cnt; j++){if(!vis[j] && mi > dis[j]){u = j;mi = dis[j];}}vis[u] = true;for(int k = 0; k < cnt; k++)if(!vis[k] && dis[k] > dis[u] + e[u][k])dis[k] = dis[u] + e[u][k];}}int main(){memset(vis, false, sizeof(vis));memset(e, 0, sizeof(e));scanf("%lf %lf %lf %lf", &nd[0].u, &nd[0].v, &nd[1].u, &nd[1].v);double u, v;int tmp = 2;cnt = 2;while(scanf("%lf %lf", &u, &v) != EOF){if(u == -1.0 && v == -1.0){for(int i = tmp; i < cnt – 1; i++){double get = get_dis(nd[i].u, nd[i].v, nd[i + 1].u, nd[i + 1].v) / 40000.0;e[i][i + 1] = e[i + 1][i] = get;}tmp = cnt;continue;}nd[cnt].u = u;nd[cnt++].v = v;}for(int i = 0; i < cnt; i++)for(int j = i + 1; j < cnt; j++)if(e[i][j] == 0)e[i][j] = e[j][i] = get_dis(nd[i].u, nd[i].v, nd[j].u, nd[j].v) / 10000.0;Dijkstra(0);printf("%d\n", (int)(dis[1] * 60.0 + 0.5));}
没有了爱的语言，所有的文字都是乏味的
