POJ 1161 - Walls

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

概要

N 個の街があり，図のように M 個の領域(外側の領域も含む)に区切られている．

街 t から領域 r へ移動するのに横切る必要がある壁の数を f(t, r) で表わしたとき， 与えられた L 個の街 t[1], ..., t[L] について，f(t[1], r) + ... + f(t[L], r) の r に関する最小値を答える．

制約

解法

領域同士の接続関係を表わすグラフをがんばって作ってワーシャル・フロイドした後，r に関する最小値を計算する．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int M, N, L;
 8   scanf("%d %d %d", &M, &N, &L);
 9   vector<int> clubs(L);
10   vector<vector<int> > adj(N);
11   for (int i = 0; i < L; i++) {
12     scanf("%d", &clubs[i]);
13     --clubs[i];
14   }
15 
16   static const int INF = 10000000;
17   vector<vector<int> > dist(M, vector<int>(M, INF));
18   for (int i = 0; i < M; i++) {
19     dist[i][i] = 0;
20   }
21   vector<int> walls(N*N, -10);
22   for (int i = 0; i < M; i++) {
23     int T;
24     scanf("%d", &T);
25     vector<int> towns(T);
26     for (int j = 0; j < T; j++) {
27       scanf("%d", &towns[j]);
28       --towns[j];
29       adj[towns[j]].push_back(i);
30     }
31     for (int j = 0; j < T; j++) {
32       int n = towns[j], m = towns[(j+1)%T];
33       if (n > m) {
34         swap(n, m);
35       }
36       const int w = n*N + m;
37       if (walls[w] < 0) {
38         walls[w] = i;
39       } else {
40         const int u = walls[w];
41         dist[u][i] = dist[i][u] = 1;
42       }
43     }
44   }
45 
46   for (int k = 0; k < M; k++) {
47     for (int i = 0; i < M; i++) {
48       for (int j = 0; j < M; j++) {
49         dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
50       }
51     }
52   }
53   int ans = INF;
54   for (int i = 0; i < M; i++) {
55     int s = 0;
56     for (vector<int>::const_iterator it = clubs.begin(); it != clubs.end(); ++it) {
57       int x = INF;
58       for (vector<int>::const_iterator jt = adj[*it].begin(); jt != adj[*it].end(); ++jt) {
59         x = min(x, dist[i][*jt]);
60       }
61       s += x;
62     }
63     ans = min(ans, s);
64   }
65   printf("%d\n", ans);
66 
67   return 0;
68 }
poj/1161.cc