PKU 2502 Subway
http://poj.org/problem?id=2502
ある地点からある地点までへの移動にかかる最短時間を求めるというような問題。
入力の処理や単位変換がめんどくさい。
vector<pair<int,double> > G[300]; PI in[300]; bool vis[300]; main(){ int sx,sy,gx,gy; cin>>sx>>sy>>gx>>gy; in[0]=mp(sx,sy); in[1]=mp(gx,gy); int x1,y1,x2,y2; int n=2; while(cin>>x1>>y1){ in[n++]=mp(x1,y1); while(cin>>x2>>y2){ if(x2==-1 && y2==-1)break; in[n++]=mp(x2,y2); int tx=x2-x1,ty=y2-y1; G[n-1].pb(mp(n-2,sqrt(tx*tx+ty*ty)/40*60)); G[n-2].pb(mp(n-1,sqrt(tx*tx+ty*ty)/40*60)); x1=x2; y1=y2; } } rep(i,n){ rep(j,i){ int tx=in[i].F-in[j].F,ty=in[i].S-in[j].S; G[i].pb(mp(j,sqrt(tx*tx+ty*ty)*6)); G[j].pb(mp(i,sqrt(tx*tx+ty*ty)*6)); } } priority_queue<pair<double,int> > q; q.push(mp(0,0)); while(!q.empty()){ int v=q.top().S; double mi=-q.top().F; q.pop(); if(vis[v])continue; vis[v]=true; if(v==1){ printf("%.0f\n",mi/1000); break; } rep(i,SZ(G[v])){ if(vis[G[v][i].F])continue; q.push(mp(-mi-G[v][i].S,G[v][i].F)); } } }