题目链接：http://poj.org/problem?id=2502
人走路的速度是10km/h，地铁的速度是40km/h题目给出一个起点，一个终点，以及几条地铁线路运行的站点。题目给的点的做坐标单位是m；答案输出从起点到终点的最短时间（分钟数）。
10km/h= 10000/60 m/min -----6/1000 min/m;
40km/h= 40000/60 m/min------3/2000 min/m;
所有点之间都可以步行到达，每条地铁的相邻两站可以相互到达，其他的都不可到达；
求起点到终点的最短路即可；
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <string>
typedef long long LL;
#define INF 1e30
#define met(a, b) memset(a, b, sizeof(a))
#define N 515 using namespace std; struct node
{
double x,y;
}a[N]; double G[N][N], dist[N];
int vis[N], cnt; double Dij(int s)
{
met(vis, );
for(int i=; i<=cnt; i++)
dist[i] = INF;
dist[s] = ;
for(int i=; i<cnt; i++)
{
double Min = INF; int Index = -;
for(int j=; j<cnt; j++)
{
if(!vis[j] && Min>dist[j])
{
Min = dist[j];
Index = j;
}
}
if(Index == -)break;
vis[Index] = ;
for(int j=; j<cnt; j++)
{
if(!vis[j] && dist[j]>dist[Index]+G[Index][j])
{
dist[j] = dist[Index]+G[Index][j];
}
}
}
return dist[];
} int main()
{
while(scanf("%lf %lf %lf %lf", &a[].x, &a[].y, &a[].x, &a[].y)!=EOF)
{
for(int i=; i<=; i++)
{
for(int j=; j<=; j++)
G[i][j] = INF;
G[i][i] = ;
}
cnt = ; int pre = -; double x, y;
while(scanf("%lf %lf", &x, &y) != EOF)
{
if(x == - && y == -)
{
pre = -;
continue;
}
a[cnt].x = x, a[cnt].y = y;
if(pre!=-)
{
double d = sqrt((a[pre].x-x)*(a[pre].x-x)+(a[pre].y-y)*(a[pre].y-y));
G[pre][cnt] = G[cnt][pre] = min(G[cnt][pre], d*3.0/);
}
pre = cnt++;
} for(int i=; i<cnt; i++)
{
for(int j=; j<cnt; j++)
{
double d = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
G[i][j] = G[j][i] = min(G[i][j],d*6.0/);
}
} double ans = Dij();
printf("%.0f\n", ans);
}
return ;
}