POJ 1122 - FDNY to the Rescue!

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

概要

頂点数 \(N\) の有効グラフが与えられる。 1つのゴールノードといくつかのスタートノードが与えられるので、各スタートノードからゴールノードまでの最短経路とその距離を答える。

制約

• \(N < 20\)

解法

ゴールノードから逆向きにダイクストラするだけ。

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   static const int INF = 10000000;
10   ios::sync_with_stdio(false);
11   int N;
12   cin >> N;
13   vector<vector<int> > m(N, vector<int>(N));
14   for (int i = 0; i < N; i++) {
15     for (int j = 0; j < N; j++) {
16       cin >> m[j][i];
17     }
18   }
19   int dest;
20   cin >> dest;
21   --dest;
22   vector<int> closest;
23   for (int n; cin >> n;) {
24     --n;
25     closest.push_back(n);
26   }
27 
28   vector<int> dist(N, INF);
29   vector<int> prev(N, -1);
30   dist[dest] = 0;
31   priority_queue<pair<int,int> > q;
32   q.push(make_pair(0, dest));
33   while (!q.empty()) {
34     const int cost = -q.top().first;
35     const int n = q.top().second;
36     q.pop();
37     if (dist[n] < cost) {
38       continue;
39     }
40     for (int i = 0; i < N; i++) {
41       if (m[n][i] == -1) {
42         continue;
43       }
44       const int cc = cost + m[n][i];
45       if (cc < dist[i]) {
46         dist[i] = cc;
47         prev[i] = n;
48         q.push(make_pair(-cc, i));
49       }
50     }
51   }
52 
53   cout << "Org\tDest\tTime\tPath" << endl;
54   vector<pair<int,int> > output;
55   for (vector<int>::const_iterator it = closest.begin(); it != closest.end(); ++it) {
56     output.push_back(make_pair(dist[*it], *it));
57   }
58   sort(output.begin(), output.end());
59   for (vector<pair<int,int> >::const_iterator it = output.begin(); it != output.end(); ++it) {
60     cout << it->second+1 << "\t" << dest+1 << "\t" << it->first;
61     for (int n = it->second; n != -1; n = prev[n]) {
62       cout << "\t" << n+1;
63     }
64     cout << endl;
65   }
66   return 0;
67 }