yukicoder No.1 道のショートカット

今日から、yukicoderの星 〜 を全埋めしていこうと思います。

No.1 道のショートカット - yukicoder

問題概要

辺のコストが費用、距離の つあるDAGにおいて、費用が 以下になるように頂点 から頂点 へ移動する(距離の)最短経路を求める。

解法

典型。状態 (頂点, 費用) を持ってダイクストラ。

int main() {
    ll N, M, K;
    cin >> N >> K >> M;
    ll A[M], B[M], C[M], D[M];
    ll DP[N][K + 1], used[N][K + 1];
    vector<pair<ll, pair<ll, ll>>> V[N];
    rep(i, M) cin >> A[i];
    rep(i, M) cin >> B[i];
    rep(i, M) cin >> C[i];
    rep(i, M) cin >> D[i];
    rep(i, M) V[A[i] - 1].pb({B[i] - 1, {C[i], D[i]}});
    rep(i, N) rep(j, K + 1) DP[i][j] = INF, used[i][j] = 0;
    rpriority_queue<pair<ll, pair<ll, ll>>> P;
    P.push({0, {0, 0}});
    while (P.size()) {
        ll t, c, d;
        t = P.top().fi, tie(c, d) = P.top().se, P.pop();
        chmin(DP[t][c], d);
        if (used[t][c]) continue;
        used[t][c] = 1;
        each(i, V[t]) {
            if (DP[i.fi][c + i.se.fi] > d + i.se.se && c + i.se.fi <= K)
                P.push({i.fi, {c + i.se.fi, d + i.se.se}});
        }
    }
    ll res = *min_element(DP[N - 1], DP[N - 1] + K + 1);
    cout << (res == INF ? -1 : res) << endl;
}