POJ 2686 - Traveling by Stagecoach

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

概要，制約

日本語の問題文を参照． Problem D: Traveling by Stagecoach

解法

• ノード
• 直前のノード

の2つ組の状態で拡張ダイクストラ．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct state
 7 {
 8   int city;
 9   double cost;
10   unsigned ticket;
11   state(int c, double d, unsigned t) : city(c), cost(d), ticket(t) {}
12   bool operator<(const state& that) const
13   {
14     return cost > that.cost;
15   }
16 };
17 
18 int main()
19 {
20   int N, M, P, A, B;
21   while (scanf("%d%d%d%d%d", &N, &M, &P, &A, &B) != EOF && N != 0) {
22     --A;  --B;
23     static int tickets[8];
24     for (int i = 0; i < N; i++) {
25       scanf("%d", &tickets[i]);
26     }
27     vector<pair<int,int> > g[30];
28     for (int i = 0; i < P; i++) {
29       int x, y, z;
30       scanf("%d%d%d", &x, &y, &z);
31       --x;  --y;
32       g[x].push_back(make_pair(y, z));
33       g[y].push_back(make_pair(x, z));
34     }
35 
36     static double dists[30][1<<8];
37     for (int i = 0; i < M; i++) {
38       fill_n(dists[i], 1<<N, 1e10);
39     }
40     dists[A][(1<<N)-1] = 0;
41     priority_queue<state> q;
42     q.push(state(A, 0.0, (1<<N)-1));
43     while (!q.empty()) {
44       const int n = q.top().city;
45       const double cost = q.top().cost;
46       const unsigned ticket = q.top().ticket;
47       q.pop();
48       if (n == B) {
49         printf("%.3f\n", cost);
50         goto NEXT;
51       }
52 
53       for (vector<pair<int,int> >::const_iterator it(g[n].begin()); it != g[n].end(); ++it) {
54         const int to = it->first;
55         const int d = it->second;
56         for (int i = 0; i < N; i++) {
57           if (ticket & (1<<i)) {
58             const unsigned s = ticket & ~(1<<i);
59             const double c = cost + static_cast<double>(d) / tickets[i];
60             if (c < dists[to][s]) {
61               dists[to][s] = c;
62               q.push(state(to, c, s));
63             }
64           }
65         }
66       }
67     }
68     puts("Impossible");
69 NEXT:
70     ;
71   }
72   return 0;
73 }