POJ_1125
問題
うわさを広げたい。ある人から他の人へうわさが伝わるのにかかる時間がそれぞれあたえられる。
この時、一番はじめに誰にうわさを吹き込めば一番早くうわさが全体に広がるかを
計算し、さらにかかる時間を求めるプログラムを作れ。
解法
重み付き有向グラフの問題。
ワーシャルフロイド法をつかって、誰のときに時間が一番短いのかをもとめればいい。
実装
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100; const int INF = 1 << 22; int G[MAX_N][MAX_N]; int N; int time, p; void solveD(){ for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) G[i][j] = min(G[i][j], G[i][k] + G[k][j]); time = INF; p = -1; for(int i = 0; i < N; i++){ int ma = 0; for(int j = 0; j < N; j++){ if(i == j) continue; ma = max(ma, G[i][j]); } if(ma < time){ p = i; time = ma; } } return; } int main(){ while(scanf("%d", &N) && N){ for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) G[i][j] = INF; for(int i = 0; i < N; i++){ int t; scanf("%d", &t); int table[2][t]; for(int j = 0; j < t; j++){ int p; scanf("%d", &p); scanf("%d", &G[i][p-1]); } } solveD(); printf("%d %d\n", p + 1, time); } return 0; }