POJ 1158 - TRAFFIC LIGHTS

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

概要

N 個のジャンクションを M 本の道が結んでいる． 道は双方向に進むことができる． ジャンクション i, j を結ぶ道は長さ l[i][j] であり，単位長さの道を進むのに単位時間掛かる．

各ジャンクションには青色と紫色からなる信号機があり，i 番目のジャンクションの信号機は青色の期間が t[i][B]，紫色の期間が t[i][P] である． また，初期状態での色が与えられ，その色である期間は r[i] である．

今いるジャンクションの信号機の色と，道を通った先のジャンクションのそれが，今いるジャンクションから出発する瞬間に一致しているときのみ進むことができる． ただし，あるジャンクションに到達した瞬間に信号機の色が変わった場合，そのジャンクションからまた別のジャンクションに出発できるかどうかは，変わった後の色で判断する．

出発するジャンクションと目的地のジャンクションが与えられるので，目的地に辿りつくまでの最小の時間を答える． 辿りつけない場合は 0 を答える．

制約

解法

ダイクストラ．しかし何秒待ってから次のノードに行けるかの計算がやや面倒．

ある信号が現在時刻 t 以降で最初に色が変わる時間を返す next_tick を書き，今いるノードと次のノードでそれぞれの next_tick 毎に時間を進めて色が一致するまでループするような実装にした．

ただし，全く同じタイミングで逆の色に変わり続けるとループが止まらなくなってしまう． このケースを忘れて最初 TLE してしまった． 問題文で連結と言っておきながら目的地に到達できないケースについて言及していたんだし，普通に気付くべき．

いつか次のノードに行けるとしたら最大で 3 回しかループし得ないので，それ以上やってもダメだったら行けないと判断するようにした．

  1 #include <cstdio>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 struct signal
  7 {
  8   bool col;
  9   int ric, tb, tp;
 10   signal(bool a, int r, int b, int p) : col(a), ric(r), tb(b), tp(p) {}
 11   bool color(int t) const
 12   {
 13     if (t < ric) {
 14       return col;
 15     } else if (col) {
 16       // initial is B
 17       return (t - ric) % (tb + tp) >= tp;
 18     } else {
 19       // initial is P
 20       return (t - ric) % (tb + tp) < tb;
 21     }
 22   }
 23   int next_tick(int t) const
 24   {
 25     if (t < ric) {
 26       return ric;
 27     } else {
 28       const int u = (t - ric) % (tb + tp);
 29       if (col) {
 30         // initial is B
 31         if (u < tp) {
 32           return t + (tp - u);
 33         } else {
 34           return t + (tp + tb - u);
 35         }
 36       } else {
 37         // initial is P
 38         if (u < tb) {
 39           return t + (tb - u);
 40         } else {
 41           return t + (tb + tp - u);
 42         }
 43       }
 44     }
 45   }
 46 };
 47 
 48 int main()
 49 {
 50   int src, dst;
 51   scanf("%d %d", &src, &dst);
 52   --src;  --dst;
 53   int N, M;
 54   scanf("%d %d", &N, &M);
 55   vector<signal> v;
 56   for (int i = 0; i < N; i++) {
 57     char c[2];
 58     int ric, tb, tp;
 59     scanf("%1s %d %d %d", c, &ric, &tb, &tp);
 60     v.push_back(signal(*c == 'B', ric, tb, tp));
 61   }
 62   vector<vector<pair<int,int> > > g(N);
 63   for (int i = 0; i < M; i++) {
 64     int u, w, l;
 65     scanf("%d %d %d", &u, &w, &l);
 66     --u;  --w;
 67     g[u].push_back(make_pair(w, l));
 68     g[w].push_back(make_pair(u, l));
 69   }
 70 
 71   priority_queue<pair<int,int> > q;
 72   q.push(make_pair(0, src));
 73   vector<int> dist(N, 10000000);
 74   dist[src] = 0;
 75   while (!q.empty()) {
 76     const int n = q.top().second;
 77     const int t = -q.top().first;
 78     q.pop();
 79     if (n == dst) {
 80       printf("%d\n", t);
 81       goto FINISH;
 82     }
 83     for (vector<pair<int,int> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
 84       const int m = it->first;
 85       const int l = it->second;
 86       int u = t;
 87       int c = 0;
 88       while (v[n].color(u) != v[m].color(u)) {
 89         const int a = v[n].next_tick(u);
 90         const int b = v[m].next_tick(u);
 91         if (a == b) {
 92           ++c;
 93           if (c == 3) {
 94             goto NEXT;
 95           }
 96         }
 97         u = min(a, b);
 98       }
 99 
100       if (u+l < dist[m]) {
101         dist[m] = u+l;
102         q.push(make_pair(-u-l, m));
103       }
104 NEXT:
105       ;
106     }
107   }
108   puts("0");
109 FINISH:
110   return 0;
111 }
poj/1158.cc