<题目链接>
题目大意：
某学生从家到学校之间有N(<200)条地铁，这个学生可以在任意站点上下车，无论何时都能赶上地铁，可以从一条地铁的任意一站到另一条地跌的任意一站，学生步行速度10km/h，地铁速度40km/h，给出学生家和学校以及每条地铁的站点坐标，求学生从家到学校的最短时间。
解题分析：
题目的难点在于建图，由于输入的点最多200个，并且所有点之间的距离都要考虑，所以用邻接矩阵存图，注意速度的单位是km/h，而路程的单位是m，并且要将地铁站点之间与普通点之间的距离区分，存好图后，直接跑一遍Dijkstra即可。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; const int MAXN=300; struct Node { double x,y; }node[MAXN]; double dis(Node a,Node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } const double INF=1e30; bool vis[MAXN]; double dist[MAXN]; double cost[MAXN][MAXN]; void Dijkstra(int n,int start) { for(int i=1;i<=n;i++) { dist[i]=INF; vis[i]=false; } dist[start]=0; int cur = 1; for (i = 0; i < n; i++) //循环n次，每次挑选没走过的到起点距离最短的点 { vis[cur] = 1; for (j = 1; j <= n; j++) { if (vis[j] == 0) dist[j] = min(dist[j], cost[cur][j] + dist[cur]); //更新每个没走过的点，到起点的最短距离 } double g = INF; int x = 1; for (j = 1; j <= n; j++) { if (dist[j] <= g && !vis[j]) { g = dist[j]; x = j; } } cur = x; } } int main() { double v1=10000.0/60; //将km/h转化为m/min，因为题目给的点坐标是m double v2=40000.0/60; while(scanf("%lf%lf%lf%lf",&node[1].x,&node[1].y,&node[2].x,&node[2].y)==4) { int n=2; int cnt1=3; int x,y; for(int i=1;i<300;i++) for(int j=1;j<300;j++) { if(i==j)cost[i][j]=0; else cost[i][j]=INF; } while(scanf("%d%d",&x,&y)==2) { if(x==-1&&y==-1) { cnt1=n+1; continue; } node[++n].x=x; node[n].y=y; if(n!=cnt1)cost[n][n-1]=cost[n-1][n]=min(cost[n][n-1],dis(node[n],node[n-1])/v2); //同一火车线，相邻站点所需花的时间 //只有相邻的站点能到 } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cost[i][j]=min(cost[i][j],dis(node[i],node[j])/v1); Dijkstra(n,1); printf("%.0lf ",(dist[2])); //%.0lf代表四舍五入 } return 0; }
2018-09-06