首页 > 代码库 > Subway---poj2502（最短路）
Subway---poj2502（最短路）
题目链接：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 515using 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, 0); for(int i=1; i<=cnt; i++) dist[i] = INF; dist[s] = 0; for(int i=1; i<cnt; i++) { double Min = INF; int Index = -1; for(int j=1; j<cnt; j++) { if(!vis[j] && Min>dist[j]) { Min = dist[j]; Index = j; } } if(Index == -1)break; vis[Index] = 1; for(int j=1; j<cnt; j++) { if(!vis[j] && dist[j]>dist[Index]+G[Index][j]) { dist[j] = dist[Index]+G[Index][j]; } } } return dist[2];}int main(){ while(scanf("%lf %lf %lf %lf", &a[1].x, &a[1].y, &a[2].x, &a[2].y)!=EOF) { for(int i=1; i<=300; i++) { for(int j=1; j<=300; j++) G[i][j] = INF; G[i][i] = 0; } cnt = 3; int pre = -1; double x, y; while(scanf("%lf %lf", &x, &y) != EOF) { if(x == -1 && y == -1) { pre = -1; continue; } a[cnt].x = x, a[cnt].y = y; if(pre!=-1) { 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/2000); } pre = cnt++; } for(int i=1; i<cnt; i++) { for(int j=1; 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/1000); } } double ans = Dij(1); printf("%.0f\n", ans); } return 0;}
Subway---poj2502（最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。