POJ 2169 - Kingdom of Magic

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

概要

頂点数 \(n\)、エッジ数 \(m\) の無向グラフが与えられ、A, B の初期位置 \(a_1, b_1\) と最終位置 \(a_2, b_2\) が与えられる。 A, B はグラフに従って最終位置まで移動するが、移動の仕方には以下の3種類がある。

さらに、移動する前後で A, B は隣接する頂点にいなければならない。 初期位置および最終位置で A, B が隣接していることは保証されている。

このとき、最終位置までの移動数の最小値と、そのときの経路を答える。

制約

解法

A, B の位置のペアを状態として普通に BFS するだけ。

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   ios::sync_with_stdio(false);
10   int N, M, a1, b1, a2, b2;
11   cin >> N >> M >> a1 >> b1 >> a2 >> b2;
12   --a1; --b1; --a2; --b2;
13   vector<vector<int> > g(N), c(N, vector<int>(N, false));
14   for (int i = 0; i < M; i++) {
15     int u, v;
16     cin >> u >> v;
17     --u;  --v;
18     g[u].push_back(v);
19     g[v].push_back(u);
20     c[u][v] = c[v][u] = true;
21   }
22   static int dist[100][100];
23   static const int INF = 10000000;
24   for (int i = 0; i < N; i++) {
25     fill_n(dist[i], N, INF);
26   }
27   dist[a1][b1] = 0;
28   static pair<int,int> prev[100][100];
29   queue<pair<int,int> > q;
30   q.push(make_pair(a1, b1));
31   prev[a1][b1] = make_pair(-1, -1);
32   while (!q.empty()) {
33     const int a = q.front().first;
34     const int b = q.front().second;
35     q.pop();
36     if (a == a2 && b == b2) {
37       break;
38     }
39     const int d = dist[a][b];
40     for (vector<int>::const_iterator it = g[a].begin(); it != g[a].end(); ++it) {
41       if (c[*it][b] && d+1 < dist[*it][b]) {
42         dist[*it][b] = d+1;
43         prev[*it][b] = make_pair(a, b);
44         q.push(make_pair(*it, b));
45       }
46     }
47     for (vector<int>::const_iterator it = g[b].begin(); it != g[b].end(); ++it) {
48       if (c[a][*it] && d+1 < dist[a][*it]) {
49         dist[a][*it] = d+1;
50         prev[a][*it] = make_pair(a, b);
51         q.push(make_pair(a, *it));
52       }
53     }
54     for (vector<int>::const_iterator it = g[a].begin(); it != g[a].end(); ++it) {
55       for (vector<int>::const_iterator jt = g[b].begin(); jt != g[b].end(); ++jt) {
56         if (!(*it == b && *jt == a) && c[*it][*jt] && d+2 < dist[*it][*jt]) {
57           dist[*it][*jt] = d+2;
58           prev[*it][*jt] = make_pair(a, b);
59           q.push(make_pair(*it, *jt));
60         }
61       }
62     }
63   }
64 
65   vector<pair<int,int> > ans;
66   for (int a = a2, b = b2; a >= 0;) {
67     ans.push_back(make_pair(a, b));
68     const pair<int,int> p = prev[a][b];
69     a = p.first;
70     b = p.second;
71   }
72   cout << dist[a2][b2] << ' ' << ans.size() << endl;
73   for (vector<pair<int,int> >::const_reverse_iterator it = ans.rbegin(); it != ans.rend(); ++it) {
74     cout << it->first+1 << ' ' << it->second+1 << endl;
75   }
76   return 0;
77 }
poj/2169.cc