POJ 1932 - XYZZY

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

概要

\(N\) 個の部屋があり、プレイヤーは1番目の部屋からスタートして \(N\) 番目の部屋のゴールを目指す。 \(M\) 本の道がそれぞれある部屋から別の部屋まで繋いでおり、一方向に移動できる。 \(i\) 番目の部屋にはエネルギー \(E_i\) が設定されており、この部屋に入るとプレイヤーのエネルギーポイントが \(E_i\) だけ増える。 同じ道や部屋を何度通っても構わない。 プレイヤーのエネルギーポイントの初期値は 100 であり、エネルギーポイントが 0 になると死んでしまう。 このとき、エネルギーポイントを切らさずにゴールまで辿りつけるかどうかを答える。

制約

解法

各部屋のエネルギーの正負を反転させれば、できるだけエネルギーを減らさずにゴールまで辿りつくことは最短経路を求めることになる。 途中で死んではダメなので、コストを更新するときにコストが 100 未満であるかどうかをチェックする。 負閉路があればそこでエネルギーをいくらでも増やせるのでゴールまで辿りつける。 そうでなければ、ゴールのコストが 100 未満になっているかを調べればよい。

ただし、これだと負閉路があってもそこからゴールまで行けない場合に困るので、 前処理としてゴールから逆向きに DFS してそもそもゴールに到達できない頂点を削っておいた。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 struct edge {
  7   int u, v;
  8   typedef int weight_type;
  9   weight_type w;
 10   edge(int s, int d, weight_type w_) : u(s), v(d), w(w_) {}
 11 };
 12 
 13 template <typename Edge>
 14 pair<vector<typename Edge::weight_type>, bool>
 15 bellman_ford(const vector<Edge>& g,/*{{{*/
 16     typename vector<Edge>::size_type N,
 17     typename vector<Edge>::size_type start,
 18     typename Edge::weight_type inf = 10000000)
 19 {
 20   /* Edge must have
 21    * - u (source node)
 22    * - v (dest node)
 23    * - w (weight)
 24    * - weight_type
 25    */
 26   typedef typename vector<Edge>::size_type size_type;
 27   typedef typename Edge::weight_type weight_type;
 28   vector<weight_type> dist(N, inf);
 29   dist[start] = 0;
 30 
 31   for (size_type i = 0; i < N; i++) {
 32     for (typename vector<Edge>::const_iterator it = g.begin(); it != g.end(); ++it) {
 33       const weight_type w = dist[it->u] + it->w;
 34       if (w < 100 && w < dist[it->v]) {
 35         dist[it->v] = w;
 36       }
 37     }
 38   }
 39 
 40   for (typename vector<Edge>::const_iterator it = g.begin(); it != g.end(); ++it) {
 41       const weight_type w = dist[it->u] + it->w;
 42     if (w < 100 && w < dist[it->v]) {
 43       return make_pair(dist, false);
 44     }
 45   }
 46   return make_pair(dist, true);
 47 }/*}}}*/
 48 
 49 void dfs(const vector<vector<int> >& g, int u, vector<int>& reachable)
 50 {
 51   if (reachable[u]) {
 52     return;
 53   }
 54   reachable[u] = true;
 55   for (vector<int>::const_iterator it = g[u].begin(); it != g[u].end(); ++it) {
 56     dfs(g, *it, reachable);
 57   }
 58 }
 59 
 60 int main()
 61 {
 62   int N;
 63   while (scanf("%d", &N) != EOF && N != -1) {
 64     vector<int> energy(N);
 65     vector<vector<int> > g(N);
 66     for (int i = 0; i < N; i++) {
 67       scanf("%d", &energy[i]);
 68       energy[i] = -energy[i];
 69       int m;
 70       scanf("%d", &m);
 71       for (int j = 0; j < m; j++) {
 72         int u;
 73         scanf("%d", &u);
 74         --u;
 75         // rev
 76         g[u].push_back(i);
 77       }
 78     }
 79 
 80     vector<int> reachable(N, false);
 81     dfs(g, N-1, reachable);
 82     vector<edge> edges;
 83     for (int i = 0; i < N; i++) {
 84       if (!reachable[i]) {
 85         continue;
 86       }
 87       for (vector<int>::const_iterator it = g[i].begin(); it != g[i].end(); ++it) {
 88         if (!reachable[*it]) {
 89           continue;
 90         }
 91         edges.push_back(edge(*it, i, energy[i]));
 92       }
 93     }
 94 
 95     const pair<vector<int>, bool> r = bellman_ford(edges, N, 0);
 96     if (!r.second || r.first[N-1] < 100) {
 97       puts("winnable");
 98     } else {
 99       puts("hopeless");
100     }
101   }
102   return 0;
103 }
poj/1932.cc