SRM624 Div1 Medium "DrivingPlans"
問題
TopCoder Statistics - Problem Statement
訳
あなたは、1からNと番号が付けられたN個の交差点を持つ町に住んでいる。町にはいくつか道路がある。それぞれの道路は双方向へ通行可能であり、2つの交差点を繋いでいる。1つの交差点をループするような道路はなく、また交差点の各ペアにおいて、それを結ぶ道路は多くても1つである。任意の2つの交差点の通行が可能となるよう、道路網が構成されている。
この町の特徴として、いくつかの道路はスピード制限がなく、そこを走るドライバーは皆とんでもないスピードを出すことだ。この問題では話を単純にするため、そのような道路を渡るときにかかる時間は0であるとする。
あなたはint N と同じ要素数を持つ3つのint配列A, B, Cが与えられる。A, B, Cは道路網の説明であり、A[i]番目の交差点とB[i]番目の交差点は道路でつながれており、その道路を渡るために要する時間はC[i]秒である。
あなたは今、1番目の交差点におり、できるだけ速くN番目の交差点へ行きたいと考えている。目的地へたどり着く方法が何通りあるかを返せ。もし、それが無限にあるのならば、-1を返せ。(2つの方法において、目的地へ行くために通った交差点の並びが違うものであれば、それは違う方法であるとする。1からNへ行くときに、どの交差点も複数回通ってよいことに注意して欲しい)
制約
2 <= N <= 2000
1 <= 道路の数 <= 2000
0 <= C[i] <= 100000
考えたこと
最短距離を出す際に、何通りあるかを計算できるよう、ダイクストラを改造する。また、頂点に時間0の道路を持つ交差点を使ったどうかのフラグも持たせてやる。
touristさんは時間0の道路を使ったかどうかは以下のように判定していた。
例えば交差点a - bの道路が時間0だとする。
ダイクストラで1からの全点最短距離とNからの全点最短距離を出しておく。
1 -> a の最短距離と、N -> bの最短距離が同じであれば、この道路を使ったことになる。
うーん・・・上手いなぁ・・・
(ひどい)ソースコード
const long long INF = 100000 * 2020; const long long MOD = 1000000009; typedef struct E { int from, to, cost; bool z; bool operator >(const E &e) const{ return cost > e.cost; } }; vector<E> G[2020]; bool resZero; long long D[2020]; long long cnt[2020]; bool zero[2020]; class DrivingPlans { public: int count(int N, vector <int> A, vector <int> B, vector <int> C) { // gruph memset(zero, false, sizeof(zero)); for (int i = 0; i < A.size(); i++) { G[A[i]].push_back(E{ -1, B[i], C[i], false }); G[B[i]].push_back(E{ -1, A[i], C[i], false }); if (C[i] == 0) { zero[A[i]] = zero[B[i]] = true; } } for (int i = 0; i <= N; i++) { D[i] = INF; } memset(cnt, 0, sizeof(cnt)); cnt[1] = 1; resZero = false; priority_queue<E, vector<E>, greater<E> > que; que.push(E{ 1, 1, 0, zero[1] }); while (!que.empty()) { E e = que.top(); que.pop(); if (e.cost > D[e.to]) continue; if (e.cost == D[e.to]) { cnt[e.to] += cnt[e.from]; cnt[e.to] %= MOD; if (e.to == N) { resZero |= e.z; } continue; } if (e.to == N) { resZero = e.z; } D[e.to] = e.cost; cnt[e.to] = cnt[e.from]; for (int i = 0; i < G[e.to].size(); i++) { E ne = G[e.to][i]; if (e.cost + ne.cost < D[ne.to]) { que.push(E{ e.to, ne.to, e.cost + ne.cost, e.z || zero[e.to] || zero[ne.to] }); } } } if (resZero) return -1; return (int)cnt[N]; } };