AtCoder Beginner Contest 164 E - Two Currencies

解説が自分には難しかったので備忘録として書きます

問題

https://atcoder.jp/contests/abc164/tasks/abc164_e

解法

頂点間の距離に加えて、金貨銀貨の設定が加わっているため一気に複雑になります。幸い頂点数と銀貨の運賃の制約が、, と抑え目になっているため、ここを生かすことを考えます。

制約からグラフは連結であることがわかるので、任意の2頂点間を移動するとき、最悪の条件でも運賃が銀貨枚である辺を本移動移動すればたどり着けることがわかります。つまり、任意の頂点にいる時のコインの枚数は枚の範囲しか持つ必要がないことがわかります。(もっと言うと運賃の最大値をとして枚の範囲)しかし、先ほどの制約からここは思い切って枚として考えてしまっても問題ないことがわかります。さて、一つの頂点上でコインを持つ状態を複数重ねるという実装をするときは、イメージ的には頂点の真上にエッジを張るようにして遷移させればよいです。要するに、頂点は頂点で銀貨を枚持つ状態を表す、として個の頂点を持つグラフを構築したのちに普通のダイクストラ法で単一始点最短路を求めればよいです。

ここからは、具体的なグラフの構築方法のまとめです。

頂点上で金貨枚を分かけて銀貨に交換するという操作を表すために、まずは頂点について、銀貨を枚持っている状態から銀貨を持っている状態へ、コストの有向辺を張るという操作をまで繰り返します。ここで注意したいのが、先ほど決めた添え字のルール上、どの頂点についても、銀貨を枚以上持つという状態を考えることができないので、がを超える場合は、辺を問答無用で銀貨枚持っている状態に繋ぎます。(ここが公式の解説で"持ちきれない銀貨は捨てる"と表現されている部分)

次に頂点,を結ぶ作業に入ります。まず、頂点の値が1-indexedだと扱いづらいので、どちらもデクリメントしておきます。次に、頂点から頂点に有向辺を結ぶ操作を考えます。移動には必ず正の枚数の銀貨を運賃として払う必要があるので、頂点で銀貨を2500枚持っている状態をはじめとして段々と枚数を下げていけばよいです。運賃は銀貨枚なので、頂点で銀貨を枚持っているとして、実際の実装では頂点から頂点にコスト(移動にかかる時間)の有向辺を張ります。頂点で銀貨の枚数が未満ならば辺は張れないことに注意しましょう。これと全く同様の操作を頂点から頂点に対しても行えば、いよいよ目的のグラフの完成です！あとは始点を決めてダイクストラ法を実行すればよいのですが、銀貨の初期値も2501以上は切り捨てるよう注意しましょう。あとはそれぞれの頂点への最短経路を求めて出力すれば終了です！お疲れ様でしたー！

コード

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
struct edge
{
    long long to;
    long long cost;
};
typedef pair<long long, long long> P; //P.first:最短距離,P.second:頂点の番号
//頂点V個の負閉路なし重み付きグラフGにおける始点sからの最短距離を求める
long long VV;
vector<vector<edge>> G;
void dijkstra(vector<long long> &dist, long long s)
{
    //greater<P>によってfirstが小さい順に取り出される
    priority_queue<P, vector<P>, greater<P>> que;
    for (long long i = 0; i < VV; i++)
        dist[i] = 1e18;
    dist[s] = 0;
    que.push(P(0, s));
    //queが空になるまで繰り返す
    while (!que.empty())
    {
        P p = que.top();
        que.pop();
        long long v = p.second;
        if (dist[v] < p.first)
            continue; //すでに最短距離ならスルー
        for (long long i = 0; i < G[v].size(); i++)
        {
            edge e = G[v][i];
            //更新作業
            if (dist[e.to] > dist[v] + e.cost)
            {
                dist[e.to] = dist[v] + e.cost;
                que.push(P(dist[e.to], e.to));
            }
        }
    }
}
int main()
{
    cout << fixed << setprecision(30);
    long long N, M, S;
    cin >> N >> M >> S;
    VV = N * 2501; //とりあえず2500枚あれば安泰(0~2500の遷移)
    G.resize(VV);  //グラフを確保
    //入力受け取り
    vector<long long> U(M), V(M), A(M), B(M);
    vector<long long> C(N), D(N);
    for (long long i = 0; i < M; i++)
    {
        cin >> U[i] >> V[i] >> A[i] >> B[i];
        U[i]--;
        V[i]--;
    }
    for (long long i = 0; i < N; i++)
        cin >> C[i] >> D[i];
    //まずは同じ頂点の上部(銀貨が多い方向)へ向かう有向辺を結ぶ
    for (long long i = 0; i < N; i++)
    {
        for (long long j = 0; j < 2500; j++)
        {
            edge e;
            if (j + C[i] >= 2501)
                e.to = i * 2501 + 2500; //行きすぎたら切り捨てる(max2500枚)
            else
                e.to = i * 2501 + (j + C[i]);
            e.cost = D[i];
            G[i * 2501 + j].push_back(e);
        }
    }
    //次に違う頂点間を渡るとき銀貨の必要枚数だけ下るような有向辺を結ぶ(頂点の最下部(銀貨0)より下にいったら結ばない)
    for (long long i = 0; i < M; i++)
    {
        //uからvへの有向辺
        for (long long j = 2500; j >= 0; j--)
        {                                  //j=2500~>0,jはuの現在のコインの枚数
            long long nextcoin = j - A[i]; //nextcoin:vの現在のコインの枚数
            if (nextcoin < 0)
                break;
            edge e;
            e.to = V[i] * 2501 + nextcoin;
            e.cost = B[i];
            G[U[i] * 2501 + j].push_back(e);
        }
        //vからuへの有向辺
        for (long long j = 2500; j >= 0; j--)
        {                                  //j=2500~>0,jはvの現在のコインの枚数
            long long nextcoin = j - A[i]; //nextcoin:uの現在のコインの枚数
            if (nextcoin < 0)
                break;
            edge e;
            e.to = U[i] * 2501 + nextcoin;
            e.cost = B[i];
            G[V[i] * 2501 + j].push_back(e);
        }
    }
    vector<long long> dist(VV);
    dijkstra(dist, min(S, 2500ll)); //頂点0でコインをmin(S,2500)持っている状態からスタート
    //都市t(t=1~>N-1)について、各コインの状態を全探索(一応)
    for (long long i = 1; i < N; i++)
    { //i=1~>N-1
        long long ans = 1e18;
        for (long long j = 0; j <= 2500; j++)
            ans = min(dist[i * 2501 + j], ans);
        cout << ans << endl;
    }
    return 0;
}