题意：
给出两个坐标，分别是小明家和小明学校的坐标。
给出多条地铁线，给出每站的坐标，已知地铁是双向的，每条线以-1 -1结尾。
给出地铁速度，步行速度。
地铁线可看成是顺次连接的线段。
求小明从家到学校用到的时间。
思路：
任何两点之间都可以连速度为步行的无向边，地铁相邻两站可以连速度为地铁速度的无向边。
之后进行SPFA；
#include<stdio.h> #include<string.h> #include<math.h> #include<queue> using namespace std; const int inf=999999999; double dis[205]; bool vis[205]; double numa=500.0/3; double numb=2000.0/3; struct node { double x,y; }; node nodes[205]; struct edge { int id; double mint; edge *next; }; edge edges[90500]; edge *adj[205]; int ednum; int num; double cal(int a,int b,double c) { return sqrt((nodes[a].x-nodes[b].x)*(nodes[a].x-nodes[b].x)+(nodes[a].y-nodes[b].y)*(nodes[a].y-nodes[b].y))/c; } inline void addEdge(int a,int b,double c) { edge *tmp; tmp=&edges[ednum]; ednum++; tmp->id=b; tmp->mint=c; tmp->next=adj[a]; adj[a]=tmp; } void SPFA() { memset(vis,0,sizeof(vis)); for(int i=1;i<num;i++) { dis[i]=inf; } queue<int>q; q.push(1); vis[1]=1; dis[1]=0; while(!q.empty()) { int tmp=q.front(); q.pop(); vis[tmp]=0; for(edge *p=adj[tmp];p;p=p->next) { if(p->mint+dis[tmp]<dis[p->id]) { dis[p->id]=p->mint+dis[tmp]; if(!vis[p->id]) { q.push(p->id); vis[p->id]=1; } } } } } int main() { for(int i=1;i<=204;i++) { adj[i]=NULL; } ednum=0; num++; scanf("%lf%lf",&nodes[num].x,&nodes[num].y); num++; scanf("%lf%lf",&nodes[num].x,&nodes[num].y); num++; while(scanf("%lf%lf",&nodes[num].x,&nodes[num].y)!=EOF) { num++; while(scanf("%lf%lf",&nodes[num].x,&nodes[num].y)) { if(nodes[num].x<0&&nodes[num].y<0) break; num++; addEdge(num-1,num-2,cal(num-1,num-2,numb)); addEdge(num-2,num-1,cal(num-1,num-2,numb)); } } for(int i=1;i<num;i++) { for(int j=1;j<i;j++) { addEdge(i,j,cal(i,j,numa)); addEdge(j,i,cal(i,j,numa)); } } SPFA(); printf("%.0lf\n",dis[2]); }
原文：http://www.cnblogs.com/tun117/p/4841856.html