POJ 2502 建图+spfa模版
九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/11895845
题意：第一行给定起末点坐标
下面每行输入地铁线路，(-1,-1)表示该线路输入结束，读到EOF
任意点都可达，速度是10km/h ,地铁线路上相邻2点速度是40km/h ，问最短时间是多少分钟
#include <cstdio>#include <cstring>#include <iostream>#include <math.h>#include <queue>#define N 250#define M N*N+2#define inf64 0x7ffffff#define inf 0x7ffffffusing namespace std;inline int Min(int a,int b){return a>b?b:a;}struct Edge{int f,t,nex;double d;}edge[M];int head[N],edgenum;double dis[N];struct node{double x,y;}p[N];double DIS(node a,node b){return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}void addedge(int u,int v,double d){Edge E={u,v,head[u],DIS(p[u],p[v])*6/(d*100)};edge[edgenum]=E;head[u]=edgenum++;}int n;void spfa(){int i,u,v;for(i=0;i<=n;i++)dis[i]=inf;bool inq[N]; memset(inq,0,sizeof(inq));dis[1]=0;queue<int>q;q.push(1);inq[1]=1;inq[2]=1;while(!q.empty()){u=q.front(); q.pop(); inq[u]=false;for(i=head[u];i!=-1;i=edge[i].nex){v=edge[i].t;if(dis[v]>dis[u]+edge[i].d){dis[v]=dis[u]+edge[i].d;if(!inq[v])q.push(v),inq[v]=1;}}}}int main(){double x,y;memset(head,-1,sizeof(head)); edgenum=0;scanf("%lf %lf %lf %lf",&p[1].x,&p[1].y,&p[2].x,&p[2].y);n=3;int now=3;while(~ scanf("%lf%lf",&x,&y))if(x==-1 && y==-1){for(int i=now;i<n-1;i++)addedge(i,i+1,40),addedge(i+1,i,40);now=n;}else {p[n].x=x, p[n].y=y;n++;}for(int i=1;i<n;i++)for(int j=1;j<n;j++)if(i!=j)addedge(i,j,10);spfa();printf("%.0lf\n",dis[2]);return 0;}/*0 0 10000 10000 200 5000 200 7000 200 -1 -1 2000 600 5000 600 10000 600 -1 -1*/