POJ 2502 SUBWAY
题目链接:http://poj.org/problem?id=2502
题目大意:求从a点到b点所需要的最短时间。
题目思路:用最短路来求,把各个点之间的时间看作所需要的路程。然后用
dij求最短路就可以了,感觉输入有点坑,还有在每条地铁线上,只有相同地铁线上的
点可以互相到达。
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; const int maxn=310; const int inf=1e9; struct nod { double x,y; }node[maxn]; double cost[maxn][maxn],dis[maxn]; bool vis[maxn]; void dij(int n,int u) { for(int i=2;i<=n;i++) { dis[i]=inf; } int start=u; vis[1]=1; for(int i=1;i<=n;i++) { dis[i]=(cost[start][i]<=dis[i])?cost[start][i]:dis[i]; } // printf("%d\n",start); for(int i=1;i<=n-1;i++) { //找到理起始点最近的点 int min=9999999; for(int i=1;i<=n;i++) { if(min>=dis[i]&&vis[i]==0) { min=dis[i]; start=i; } } vis[start]=1; for(int i=1;i<=n;i++) { if(vis[i]!=1) dis[i]= (dis[i]<=(dis[start]+cost[start][i]))?dis[i]:(dis[start]+cost[start][i]); } } } double dist(nod a,nod b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main() { double v1=10000.0/60; double v2=40000.0/60; scanf("%lf%lf%lf%lf",&node[1].x,&node[1].y,&node[2].x,&node[2].y); int n=2; int cnt1=3; for(int i=1;i<=300;i++) { for(int j=1;j<=300;j++) { if(i==j) cost[i][j]=0; else cost[i][j]=inf; } } double x,y; while(scanf("%lf%lf",&x,&y)) { if(x==-1&&y==-1) { cnt1=n+1; break; } n++; node[n].x=x; node[n].y=y; if(n!=cnt1) cost[n][n-1]=cost[n-1][n]=min(cost[n][n-1],dist(node[n],node[n-1])/v2); } while(scanf("%lf%lf",&x,&y)!=EOF) { n++; node[n].x=x; node[n].y=y; while(scanf("%lf%lf",&x,&y)!=EOF) { if(x==-1&&y==-1) break; n++; node[n].x=x; node[n].y=y; } if(n!=cnt1) cost[n][n-1]=cost[n-1][n]=min(cost[n][n-1],dist(node[n],node[n-1])/v2); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cost[i][j]=min(cost[i][j],dist(node[i],node[j])/v1); } } dij(n,1); printf("%d\n",(int)(dis[2]+0.5)); return 0; }