POJ 1125 - Stockbroker Grapevine

http://poj.org/problem?id=1125

概要

N 人の stockbroker について，ある人 i からある人 j まで噂を伝えるのにかかる時間 t[i][j] が与えられる．

全体に噂が広まるのにかかる時間を最小にしたい． そのときに最初に噂を伝えるべき人と，かかる時間を出力する． ただし，どの人に伝えても全体に噂が広まらないときは「disjoint」と出力する．

制約

• 1 <= N <= 100
• 1 <= t[i][j] <= 100

解法

ワーシャルフロイドした後，自分以外の人への最短経路の最大値が最小になる人が答え．

 1 #include <iostream>
 2 #include <vector>
 3 #include <limits>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 template<typename T, typename F> 
 8 vector<vector<T> > floyd(const vector<vector<pair<int,T> > >& g, const F& f)
 9 {
10   const int N = g.size();
11   vector<vector<T> > dist(N, vector<T>(N, numeric_limits<T>::max()/N));
12   for (int i = 0; i < N; i++) {
13     for (int j = 0; j < g[i].size(); j++) {
14       const int to = g[i][j].first;
15       dist[i][to] = g[i][j].second;
16     }
17   }
18 
19   for (int k = 0; k < N; k++) {
20     for (int i = 0; i < N; i++) {
21       for (int j = 0; j < N; j++) {
22         dist[i][j] = min(dist[i][j], f(dist[i][k], dist[k][j]));
23       }
24     }
25   }
26   return dist;
27 }
28 
29 int main()
30 {
31   int N;
32   while (cin >> N && N != 0) {
33     vector<vector<pair<int,int> > > g(N);
34     for (int i = 0; i < N; i++) {
35       int n;
36       cin >> n;
37       for (int j = 0; j < n; j++) {
38         int s, c;
39         cin >> s >> c;
40         g[i].push_back(make_pair(s-1, c));
41       }
42     }
43 
44     const vector<vector<int> > dist = floyd(g, plus<int>());
45     int ans_start, ans_dist = numeric_limits<int>::max();
46     for (int i = 0; i < N; i++) {
47       int m = 0;
48       for (int j = 0; j < N; j++) {
49         if (i != j) {
50           m = max(m, dist[i][j]);
51         }
52       }
53       if (ans_dist > m) {
54         ans_start = i+1;
55         ans_dist = m;
56       }
57     }
58     if (ans_dist == numeric_limits<int>::max()) {
59       cout << "disjoint" << endl;
60     } else {
61       cout << ans_start << ' ' << ans_dist << endl;
62     }
63   }
64 }