POJ 1603 - Risk

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

概要

20 個の国の隣接関係が与えられたとき，ある国から別のある国までの最短距離を答える．

制約

解法

ワーシャルフロイドするだけ．

入力の最後を検知するのが若干めんどい．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int X;
 8   for (int Ti = 1; cin >> X; Ti++) {
 9     static const int M = 20;
10     int dist[M][M];
11     for (int i = 0; i < M; i++) {
12       fill_n(dist[i], M, 1000000);
13     }
14 
15     for (int j = 0; j < X; j++) {
16       int u;
17       cin >> u;
18       --u;
19       dist[0][u] = dist[u][0] = 1;
20     }
21     for (int i = 1; i < M-1; i++) {
22       cin >> X;
23       for (int j = 0; j < X; j++) {
24         int u;
25         cin >> u;
26         --u;
27         dist[i][u] = dist[u][i] = 1;
28       }
29     }
30 
31     for (int k = 0; k < M; k++) {
32       for (int i = 0; i < M; i++) {
33         for (int j = 0; j < M; j++) {
34           dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
35         }
36       }
37     }
38 
39     int N;
40     cin >> N;
41     cout << "Test Set #" << Ti << endl;
42     while (N-- > 0) {
43       int u, v;
44       cin >> u >> v;
45       cout << u << " to " << v << ": " << dist[u-1][v-1] << endl;
46     }
47     cout << endl;
48   }
49   return 0;
50 }
poj/1603.cc