POJ2502 Subway(最短路径)

题意：

从家到学校，给出家和学校的坐标，可以做地铁或走路，走路10KM/H，坐地铁40KM/H，地铁有很多条线路，每条线路之间有很多站点，给出每个站点的坐标（都是整数），要求到学校需要最短的分钟数（四舍五入后取整）

要点：

这题的输入简直日了狗了，线路的数目是以EOF结尾的，完全没办法验证数据。简单的说就是用一个map数组存储从点i到j需要的时间，然后Floyd模板即可。关键这个map数组不好做，同一条线路中相邻的站点可以用地铁方式算（不算每条线路的第一个站点，地铁只能一站一站的到），如果不相邻就用步行即可。

#include<iostream>
#include<cmath>
#include<string>
#include<cstdlib>
#include<algorithm>
#define d double	//注意sqrt输出的形式要与因子匹配，要输出double因子要都是double
#define distance(t,s) sqrt(((d)t.x-(d)s.x)*((d)t.x-(d)s.x)+((d)t.y-(d)s.y)*((d)t.y-(d)s.y))
using namespace std;
int x[405], y[405];
double map[405][405];//记录到点之间需要的时间
struct node
{int x, y;
}p[500];void floyd(int n)
{for (int k = 1; k < n; k++)for (int i = 1; i < n; i++)for (int j = 1; j < n; j++)if (map[i][j]>map[i][k] + map[k][j])map[i][j] = map[i][k] + map[k][j];
}int main()
{int a,b;scanf("%d%d%d%d", &p[1].x, &p[1].y, &p[2].x, &p[2].y);//点都是非负整数map[2][1] = map[1][2] = distance(p[1], p[2])*60.0/10000.0;int n = 3, j = 0;while (scanf("%d%d", &a, &b) != EOF){if (a == -1 && b == -1)j = 0;	//j=0说明不在同一条线路中，也就是每条线路中第一个站点不用与前一个计算else {p[n].x = a, p[n].y = b;for (int i = 1; i < n - j; i++)			//计算所有点到当前点的步行时间map[i][n] = map[n][i] = distance(p[i],p[n])*60.0/10000.0;for (int i = n - j; i<n; i++)			//地铁时一直与前一个相邻的计算map[i][n] = map[n][i] = distance(p[i],p[n])*60.0/40000.0;j = 1, n++;	}}floyd(n);printf("%d\n", (int)(map[1][2]+0.5));//最后输出舍入后的整数分钟数。return 0;
}