Saving Snuuk [SoundHound Inc. Programming Contest 2018 -Masters Tournament- D]

https://beta.atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d

考察過程

1. 何から手をつけていいかわからない感じがある
2. 何か固定できないか考えよう
3. 両替地点iを固定すると、頂点sから頂点iへは最短経路、頂点iから頂点tへも最短経路が好ましい
4. 頂点iから頂点tへの最短経路は、頂点tから頂点iへの最短経路に等しい
5. 頂点sと頂点tから全頂点への最短経路をダイクストラで求めておけば、頂点iで両替したときの最短減額が得られる
6. i年後に両替所として使えるのは、頂点i～N-1である
7. これは累積minとかで高速に得られる

解法

https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2817915

最大額を求めるのではなく、必要な最短経路を求めることにする。
　
頂点Sから頂点iまで円を使って移れる最短経路をDA[i]
頂点Tから頂点iまでスヌークを使って移れる最短経路をDB[i]
とすると、頂点iで両替をしたときの最短経路をdp[i]はdp[i] = DA[i] + DB[i]となる。
（変数名がdpなのは意味がないです。DPは使いません）
　
DAとDBはダイクストラで計算できる。
よってdpは計算できる。
　
これを「dp[i] = 頂点i～N-1で両替をしたときの最短経路」に変換する。
累積minの要領で、dp[i] = min(dp[i], dp[i+1])で更新すればよい。
あとは最大額に変換すれば答え。

int N, M, S, T;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//---------------------------------------------------------------------------------------------------
int vis[101010];
void dijk(int s, vector<vector<pair<int,int>>> &E, vector<ll> &D) {
    rep(i, 0, N) D[i] = infl;
    rep(i, 0, N) vis[i] = 0;
 
    min_priority_queue<pair<ll, int>> que;
 
    D[s] = 0;
    que.push({ 0, s });
 
    while (!que.empty()) {
        auto q = que.top(); que.pop();
 
        ll cst = q.first;
        int cu = q.second;
 
        if (vis[cu]) continue;
        vis[cu] = 1;
 
        fore(p, E[cu]) {
            ll cst2 = cst + p.second;
            int to = p.first;
 
            if (chmin(D[to], cst2)) que.push({ D[to], to });
        }
    }
}
//---------------------------------------------------------------------------------------------------
ll dp[101010];
void _main() {
    cin >> N >> M >> S >> T;
    S--; T--;
 
    vector<vector<pair<int, int>>> EA(N);
    vector<vector<pair<int, int>>> EB(N);
    vector<ll> DA(N), DB(N);
 
    rep(i, 0, M) {
        int u, v, a, b; cin >> u >> v >> a >> b;
        u--; v--;
 
        EA[u].push_back({ v, a });
        EA[v].push_back({ u, a });
 
        EB[u].push_back({ v, b });
        EB[v].push_back({ u, b });
    }
    
    dijk(S, EA, DA);
    dijk(T, EB, DB);
 
    rep(i, 0, N) dp[i] = DA[i] + DB[i];
    rrep(i, N - 2, 0) chmin(dp[i], dp[i + 1]);
 
    ll ma = 1;
    rep(i, 0, 15) ma *= 10;
    rep(i, 0, N) dp[i] = ma - dp[i];
    rep(i, 0, N) printf("%lld\n", dp[i]);
}