首页 > 代码库 > Subway POJ 2502
Subway POJ 2502
题目链接:
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 520struct 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=0; i<=n; i++) { dist[i] = INF; }}void Input(){ int k = 2; n = 2; scanf("%lf%lf%lf%lf",&P[0].x,&P[0].y,&P[1].x,&P[1].y); P[0].k = 0, P[1].k = 1; while(scanf("%lf%lf",&P[n].x, &P[n].y) != EOF ) { n ++; P[n-1].k = k; if( P[n-1].x == -1 && P[n-1].y == -1) { n --; k ++; } } for(int i=0; i<n; i++) { for(int j=0; j<=i; j++) { double len = Len(P[i], P[j]), time; time = len / 10000.0 * 60; if(P[i].k == P[j].k && i == j+1 ) { time = len / 40000.0 * 60; } G[i][j] = time; G[j][i] = G[i][j]; } }}double Spfa(){ int e = 0; queue<int> Q; dist[0] = 0; Q.push(e); while( !Q.empty() ) { e = Q.front(); Q.pop(); vis[e] = false; for(int i=0; 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[1];}int main(){ Input(); Init(); double ans = Spfa(); printf("%0.lf\n",ans); return 0;}
Subway POJ 2502
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。