题目链接:
http://poj.org/problem?id=2502
题目大意：
你刚从一个安静的小镇搬到一个吵闹的大城市，所以你不能再骑自行车去上学了，只能乘坐地铁或者步行去上学。因为你不想迟到，所以你想知道自己多长时间能到达学校，你步行的速度是 10km/h，
地铁的速度是40km/h, 假如你是幸运的，你刚到地铁就有一辆地铁行驶过来， 你马上就可以乘坐， 任意的一个地铁你可以乘坐多次，若果你愿意你可以换乘不同的地铁，所有的地铁都是两个方向的。
输入：
输入首先包含两个坐标，表示你家的坐标和学校的坐标，随后有几个规格的地铁线路， 每个地铁线路包含几个坐标， 每个坐标表示地铁的站台，地铁到这个坐标时会停止， 你可以假设地铁站之间是直线。给个坐标都是整数，每个地铁线路至少有两站，最后两个 -1 代表地铁的站结束，最多有200站，
输出：
输出一个分钟数，表示家到学校的最短时间。结果四舍五入
题目分析：
这题目难点就是在处理数据问题上，其他的都简单，但是有点是要注意的就是 铁路线的每个站点 并不是直线， 有可能是曲线， 因此在算距离的时候地铁的两个点并不能全部以直线距离来算
代码：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
#define INF 0xffffffff
#define maxn 520 struct Point
{
double x, y;
int k;
}P[maxn]; bool vis[maxn];
int n;
double G[maxn][maxn], dist[maxn];
double Len(Point A, Point B)
{
return sqrt( 1.0*(A.x - B.x)*(A.x - B.x) + 1.0*(A.y - B.y)*(A.y - B.y) );
}
void Init()
{
memset(vis,false,sizeof(vis));
for(int i=; i<=n; i++)
{
dist[i] = INF;
}
}
void Input()
{
int k = ;
n = ; scanf("%lf%lf%lf%lf",&P[].x,&P[].y,&P[].x,&P[].y);
P[].k = , P[].k = ; while(scanf("%lf%lf",&P[n].x, &P[n].y) != EOF )
{
n ++;
P[n-].k = k; if( P[n-].x == - && P[n-].y == -)
{
n --;
k ++;
}
} for(int i=; i<n; i++)
{
for(int j=; j<=i; j++)
{
double len = Len(P[i], P[j]), time; time = len / 10000.0 * ; if(P[i].k == P[j].k && i == j+ )
{
time = len / 40000.0 * ;
} G[i][j] = time;
G[j][i] = G[i][j];
}
}
}
double Spfa()
{
int e = ; queue<int> Q; dist[] = ;
Q.push(e); while( !Q.empty() )
{
e = Q.front();
Q.pop(); vis[e] = false; for(int i=; i<n; i++)
{
if(dist[i] > dist[e] + G[e][i])
{
dist[i] = dist[e] + G[e][i]; if(!vis[i])
{
vis[i] = true;
Q.push(i);
}
}
}
}
return dist[];
} int main()
{ Input(); Init(); double ans = Spfa(); printf("%0.lf\n",ans); return ;
}