当前位置: 代码迷 >> 综合 >> POJ2502 Subway(最短路径)
  详细解决方案

POJ2502 Subway(最短路径)

热度:67   发布时间:2024-01-16 13:45:22.0

题意:

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

要点:

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


15385076 Seasonal 2502 Accepted 832K 141MS C++ 1142B 2016-04-13 08:08:56
#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;
}