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;
}