WARush

SRMの結果とか、解けた問題のコードを書いていきます

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];
    }
};