Yukicoder001 道のショートカット

毎日解いた分の問題全部の解説を自分用に書いていたのですが、どうせならホームページに書いていこうと思って書いていくことにしました。

問題概要

$N$個の街があり、$V$個の道路がある。各道路にはコストと通過するのにかかる単位時間が定められている。 今$C$までのコストを使っても良いので$1$から$N$の街へ移動するのに必要な最小の単位時間を答えよ。

yukicoder001

解法

拡張ダイクストラの類の問題。 次の頂点に移動する場合に同じ距離に対しても別のコストが存在する可能性がある。 このようなときは頂点をコストの種類だけ持つようにしてあげれば複数の状態の頂点をもつことができる。 これは $dist$[ 現在使用したコストの総和$c$ ][ いまいる頂点 ]:= 今いる頂点で使用したコストが$c$であるときの最短距離(時間) として遷移してあげればよい。

$N$とか$V$とかわかりにくいので適宜変数を変えるとバグりにくそう。

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    
    LL N,C,V;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N >> C>>V;
        VI s(V), t(V), y(V), m(V);
    
        FOR(i, 0, V) {
            cin >> s[i]; s[i]--;
        }
        FOR(i, 0, V) {
            cin >> t[i]; t[i]--;
        }
        FOR(i, 0, V) {
            cin >> y[i];
        }
        FOR(i, 0, V) {
            cin >> m[i];
        }
        // sum m[i]を最小化　成約はC
        using tp = tuple<int, int, int>;
        vector<vector< tp >> G(N);
        FOR(i, 0, V) {
            G[s[i]].push_back(tp(t[i], y[i], m[i]));
        }
        VVI dist(N, VI(C+1, INF));
        dist[0][0] = 0;
        priority_queue<tp,vector<tp>,greater<tp>> pq;
        pq.push(tp(0,0,0)); // d,c,v
        while (!pq.empty()) {
            tp a = pq.top(); pq.pop();
            int d, c, v; tie(d, c, v) = a;
            if (dist[v][c] < d)continue;
            FOR(i, 0, SZ(G[v])) {
                int nv, adc, adt;
                tie(nv, adc, adt) = G[v][i]; // nv,y,m
                if (adc + c > C)continue;
                if (dist[nv][adc + c] > dist[v][c] + adt) {
                    dist[nv][adc + c] = dist[v][c] + adt;
                    pq.push(tp(dist[nv][adc+c] , adc+c, nv));
                }
            }
        }
        ans = INF;
        FOR(i, 0, C + 1) {
            ans = min(ans, (LL)dist[N - 1][i]);
        }
        
        cout << (ans== INF? -1:ans) << "\n";
    
        return 0;
    }