题目链接:http://poj.org/problem?id=2502
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #include <iomanip> using namespace std; const int MAXN=300; const double INF=999999; bool visited[MAXN]; double dist[MAXN]; double map[MAXN][MAXN]; struct Node{ double x,y; }p[MAXN]; double dis(Node a,Node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void relax(int u,int v){ double tmp=dist[u]+map[u][v]; if(tmp<dist[v]) dist[v]=tmp; } void dij(int n,int start) { for(int i=1;i<=n;i++) { dist[i]=INF; visited[i]=false; } //把这个地方用memset表示答案就会不一样 dist[start]=0; for(int j=0;j<n;j++) { int k=-1; double Min=INF; for(int i=1;i<=n;i++) if(!visited[i]&&dist[i]<Min) { Min=dist[i]; k=i; } if(k==-1)break; visited[k]=true; for(int i=1;i<=n;i++) if(!visited[i]) relax(k,i); } } int main() { double v1=10000.0/60; double v2=40000.0/60; while(cin>>p[1].x>>p[1].y>>p[2].x>>p[2].y) { int n=2; int cnt1=3; int x,y; for(int i=1;i<MAXN;i++) for(int j=1;j<MAXN;j++) { if(i==j)map[i][j]=0; else map[i][j]=INF; } while(cin>>x>>y) { if(x==-1&&y==-1) { cnt1=n+1; continue; } n++; p[n].x=x; p[n].y=y; if(n!=cnt1) map[n][n-1]=map[n-1][n]=dis(p[n],p[n-1])/v2; //这句不一定要min //dis(p[n],p[n-1])/v2为地铁时间 } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=min(map[i][j],dis(p[i],p[j])/v1); //这句一定要min //dis(p[i],p[j])/v1为步行时间 dij(n,1); // int ans=(int)round(dist[2]); // (int)round(dist[2]); // cout<<ans<<endl; cout<<setprecision(2); cout<<dist[2]<<endl; } return 0; }