RUPC (Ritsumeikan University Programming Contest) 2011 Problem C Seishun 18 Kippu
問題
重みつきの無向グラフが与えられる。
スタートから、中間の頂点を通ってゴールまでたどり着くのにかかる最短時間を求めよ。
制約条件
頂点の数≦500
方針
ワーシャルフロイドにより全点間最短路を求める。
その後、スタートと中間の最短距離と中間からゴールの最短距離を足す。
ソースコード
int dist[500][500]; int main() { int n,m; while(cin>>n>>m,n){ map<string,int> id; int k=0; string s,p,g; cin>>s>>p>>g; if(!id.count(s))id[s]=k++; if(!id.count(p))id[p]=k++; if(!id.count(g))id[g]=k++; rep(i,n)rep(j,n)dist[i][j]=inf; rep(i,m){ string a,b; int d,t; cin>>a>>b>>d>>t; if(!id.count(a))id[a]=k++; if(!id.count(b))id[b]=k++; dist[id[a]][id[b]]=dist[id[b]][id[a]]=d/40+t; } rep(k,n)rep(i,n)rep(j,n)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); cout<<dist[id[s]][id[p]]+dist[id[p]][id[g]]<<endl; } return 0; }