POJ 2267 - From Dusk till Dawn or: Vladimir the Vampire

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

概要

N 個の駅があり，吸血鬼がある駅から別の駅まで電車を乗り継いで移動する．

全体で M 本の電車があり，それぞれ

が設定されている．

吸血鬼は18時から次の日の6時までの間しか移動できない． すなわち，18時よりも前に出発する電車や，6時よりも後に到着する電車には乗ることができない．

吸血鬼は移動できない間は駅にずっといることになり，正午になると血液を1リットル飲む．

飲む血液の量が最小になるように目的地まで進んだとき，飲んだ血液の量を答える．

ただし，目的地に辿り着けない場合は「There is no route Vladimir can take.」と答える．

制約

解法

ダイクストラするだけ．

「18時から6時」はやりにくいので，18時が0時に，6時が12時になるように正規化した．

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 #include <queue>
  5 using namespace std;
  6 
  7 struct edge { int to, dep, time; };
  8 
  9 struct state
 10 {
 11   int idx, cost, hour;
 12   state(int i, int c, int h) : idx(i), cost(c), hour(h) {}
 13   bool operator<(const state& that) const
 14   {
 15     if (cost != that.cost) {
 16       return cost > that.cost;
 17     } else {
 18       return hour > that.hour;
 19     }
 20   }
 21 };
 22 
 23 int main()
 24 {
 25   int T;
 26   cin >> T;
 27   for (int Ti = 1; Ti <= T; Ti++) {
 28     int M;
 29     cin >> M;
 30     map<string,int> dict;
 31     vector<vector<edge> > g;
 32     for (int i = 0; i < M; i++) {
 33       string from, to;
 34       edge e;
 35       cin >> from >> to >> e.dep >> e.time;
 36       e.dep %= 24;
 37       if (e.dep >= 18) {
 38         e.dep -= 18;
 39       } else {
 40         e.dep = (e.dep + 6);
 41       }
 42 
 43       if (e.dep + e.time > 12) {
 44         continue;
 45       }
 46       if (!dict.count(from)) {
 47         dict.insert(make_pair(from, dict.size()));
 48         g.push_back(vector<edge>());
 49       }
 50       if (!dict.count(to)) {
 51         dict.insert(make_pair(to, dict.size()));
 52         g.push_back(vector<edge>());
 53       }
 54       e.to = dict[to];
 55       g[dict[from]].push_back(e);
 56     }
 57     const int N = g.size();
 58 
 59     string from, to;
 60     cin >> from >> to;
 61     cout << "Test Case " << Ti << "." << endl;
 62     if (!dict.count(from) || !dict.count(to)) {
 63       cout << "There is no route Vladimir can take." << endl;
 64       continue;
 65     }
 66     const int start = dict[from], goal = dict[to];
 67     static const int INF = 10000000;
 68     vector<vector<int> > dist(N, vector<int>(24, INF));
 69     priority_queue<state> q;
 70     q.push(state(start, 0, 0));
 71     dist[start][0] = 0;
 72     int ans = INF;
 73     while (!q.empty()) {
 74       const int cost = q.top().cost;
 75       const int n = q.top().idx;
 76       const int h = q.top().hour;
 77       q.pop();
 78       if (n == goal) {
 79         ans = min(ans, cost);
 80         continue;
 81       }
 82       if (cost < dist[n][h]) {
 83         continue;
 84       }
 85 
 86       for (vector<edge>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
 87         if (h <= it->dep) {
 88           const int nn = it->to;
 89           const int hh = it->dep + it->time;
 90           if (cost < dist[nn][hh]) {
 91             dist[nn][hh] = cost;
 92             q.push(state(nn, cost, hh));
 93           }
 94         }
 95       }
 96       if (cost+1 < dist[n][0]) {
 97         dist[n][0] = cost+1;
 98         q.push(state(n, cost+1, 0));
 99       }
100     }
101     if (ans == INF) {
102       cout << "There is no route Vladimir can take." << endl;
103     } else {
104       cout << "Vladimir needs " << ans << " litre(s) of blood." << endl;
105     }
106 NEXT:
107     ;
108   }
109   return 0;
110 }
poj/2267.cc