PKU1125-Stockbroker Grapevine

解法

ダイクストラ法．結局全点間最短距離に帰着されるのでワーシャルフロイド法の方が賢い．

実装(C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int N;
int G[100][100];
int mintime[100];
int solve(int s){
	fill(mintime,mintime+N,9999999);
	mintime[s]=0;
	typedef pair<int,int> P;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
	while(!que.empty()){
		P t=que.top();que.pop();
		if(mintime[t.second]<t.first)continue;
		for(int i=0;i<N;i++){
			if(G[t.second][i]>0){
				int nt=G[t.second][i]+t.first;
				if(mintime[i]>nt){
					mintime[i]=nt;
					que.push(P(nt,i));
				}
			}
		}
	}
	return *max_element(mintime,mintime+N);
}
int main() {
	while(scanf("%d",&N),N){
		memset(G,0,sizeof(G));
		for(int i=0;i<N;i++){
			int k;
			scanf("%d",&k);
			for(int j=0;j<k;j++){
				int a,b;
				scanf("%d%d",&a,&b);a--;
				if(G[i][a]==0)G[i][a]=b;else G[i][a]=min(G[i][a],b);
			}
		}
		int ans_start=-1,answer=9999999;
		for(int i=0;i<N;i++){
			int t=solve(i);
			if(t<answer){
				answer=t;
				ans_start=i;
			}
		}
		if(answer>999999){
			puts("disjoint");
		}else{
			printf("%d %d\n",ans_start+1,answer);
		}
		fflush(stdout);
	}
	return 0;
}