题意：在一个城市里，分布着若干条地铁线路，每条地铁线路有若干个站点，所有地铁的速度均为40km/h。现在你知道了出发地和终点的坐标，以及这些地铁 线路每个站点的坐标，你的步行速度为10km/h，且你到了地铁的任意一个站之后就刚好有地铁出发。问你从出发点到终点最少需要多少时间。
有很多站点，给的数据只是一条条线路，所以需要先预处理数据，增加任意两点人走需要的时间。数据预先处理比较麻烦......
#include<stdio.h> #include<vector> #include<stack> #include<algorithm> #include< string.h> #include<math.h> using namespace std; const int maxn = 100005; const int oo = 0xfffffff; const double vs = 40* 1000/ 60.0; // 每分钟走多少米 const double vp = 10* 1000/ 60.0; struct node { int u, v, next; double c; // 两点之间所需时间 }e[maxn]; struct point { int x, y; }p[ 1005]; int nPoint, head[ 1005]; double dis[ 1005]; bool vis[ 1005]; double Len(point a, point b, double v) { return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ) / v; } void Add( int u, int v, double len, int k) { e[k].u = u; e[k].v = v; e[k].c = len; e[k].next = head[u]; head[u] = k; } void spfa() { stack< int> sta; sta.push( 1); while(sta.size()) { int i = sta.top();sta.pop(); vis[i] = false; for( int j=head[i]; j!= 0; j=e[j].next) { int u = e[j].u, v = e[j].v; double c = e[j].c; if(dis[u]+c < dis[v]) { dis[v] = dis[u] + c; if(vis[v] == false) { vis[v] = true; sta.push(v); } } } } } int main() { int i, j, flag= 0, k= 1; scanf( " %d%d%d%d ", &p[ 1].x, &p[ 1].y, &p[ 2].x, &p[ 2].y); nPoint = 3; while(scanf( " %d%d ", &p[nPoint].x, &p[nPoint].y) != EOF) { if(p[nPoint].x != - 1) { if(flag == 0) flag = 1; else { double c = Len(p[nPoint], p[nPoint- 1], vs); Add(nPoint, nPoint- 1, c, k++); Add(nPoint- 1, nPoint, c, k++); } nPoint++; } else flag = 0; } for(i= 1; i<nPoint; i++) for(j=i+ 1; j<=nPoint; j++) { double c = Len(p[i], p[j], vp); Add(i, j, c, k++); Add(j, i, c, k++); } for(i= 2; i<nPoint; i++) dis[i] = oo; spfa(); printf( " %.0f\n ", dis[ 2]); return 0; }