【ABC214】C - Distribution

atcoder.jp

解法

この問題は、0→iに重み$ T_i $の辺と、i→i+1に重み$ S_i $の辺があるグラフと見ることができます。
ここで、0とは高橋君のことを指します。

これで、頂点0からiまでの最短距離は？という問題に変換することができました。
これはダイクストラ法で解くことができます。

実装

whileを回す前にqueueに0→iの辺を通った後の頂点を放り込んでしまって問題ありません。

void solve(long long N, std::vector<long long> S, std::vector<long long> T) {
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
    vector<ll> dist(N, INF64);
    REP (i, N) {
        dist[i] = T[i];
        que.push({T[i], i}); // 高橋くんがi番目のすぬけくんに宝石を渡すことを表す
    }
    
    
    while (!que.empty()) {
        ll d = que.top().first;
        ll p = que.top().second;
        que.pop();

        if (d > dist[p]) continue;

        if (p == N-1) {
            if (chmin(dist[0], d + S[p])) que.push({dist[0], 0}); // 最初に戻る
        } else {
            if (chmin(dist[p+1], d + S[p])) que.push({dist[p+1], p+1}); // 一つ隣へ
        }
    }

    REP (i, N) {
        c(dist[i]) // 出力
    }
}