Educational Codeforces Round 102(Div. 2) E Minimum Path

解説見たけど解けねえーーー！っていう気分になった。拡張ダイクストラ、もっと抽象化して理解する必要があるなあ。

拡張ダイクストラもそうだし、区間DPとかあの辺何回勉強しても深い理解が出来ていないので頑張らないといけませんね。

問題概要

Problem - E - Codeforces

普通にグラフの最短距離を考えるのは簡単だから、今まで通ってきた辺の集合をとして

を最短距離の代わりに求めろという問題。

解法

どちみち最短経路なので、工夫してダイクストラをするしかないなあというお気持ちになる。試しにsumとmaxとminを持つダイクストラしてみたけどダメだった。

拡張ダイクストラの基本はよくけんちょんさんとかがDP入門の記事で言うのと同じように、「今持っている情報じゃ解けないから次元を増やす」ことだと思う。
そこでDPの次元拡張と同じような気持ちになって考えると、頂点数も辺の数も だし、重みに至ってはなのであまり大きく次元を増やせそうにはないことがわかる。

何か良い性質はないか数式をグッと睨む。
するとこれって結局、ダイクストラする中で一回だけコストが無料になって、一回だけコストが倍になった時の最小値を求めろという話と同値であることがわかる。難しくないか？？？言われればまあそうなんだけど。

ということは次元を三つに拡張して、dp[i][j][k] := i番目の頂点に来ていて、コストが既に倍になっているかどうか(j: bool)、コストが既に無料になっているかどうか(k: bool)とすればこの問題を解くことが出来る。

ここまで言われたらダイクストラかDPにある程度慣れている緑コーダーでも解けそうな見た目になったね。
まあ実装がtuple地獄で嫌な気持ちになるんですけど......。

拡張ダイクストラはまあみんなすぐだと思うんだけど、そこから数式の条件を言い換えるのが一番の難所。maxやminがあったらそれを手がかりに考えがちなんだけど、もう少し広く考えることを覚えた。

「こういう発想があった」ということを覚えておかないと一生式変形しちゃう気がするな。

この問題、数式が何か良い感じに式変形すると嬉しくなれそうな、微妙に意味ありげな形をしているので、それでかなり考えてしまった.....。
思考の紛れを誘う要素が多いっていうか、定数個しか次元を拡張できない縛りもあって、実は式を良い感じにすると普通のダイクストラで解けるんじゃないかみたいな方針に行ってしまう。

方針ガチャで当たりを引いてもしっかりそれを詰め切れなければ意味がないので、出来るだけ確実な思考の筋道をここで言語化しておきたかった。けどこれはもう把握しておくしかないかも。

以下コード

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

struct Edge {
    ll to, cost;
    Edge(){}
    Edge(ll to, ll cost): to(to), cost(cost){}
};

//           dist, v, fl_free, fl_doulbe
typedef tuple<ll, int, bool, bool> T;
int main(int argc, char const *argv[]) {
    input_init();
    int n,m; cin>>n>>m;
    vector<vector<Edge>> g(n);
    rep(i,m) {
        ll a,b,w; cin>>a>>b>>w; --a,--b;
        g[a].emplace_back(b,w);
        g[b].emplace_back(a,w);
    }

    priority_queue<T, vector<T>, greater<>> pq;
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(2, vector<ll>(2, LINF)));

    dp[0][0][0] = 0;
    pq.emplace(0,0,false,false);

    while (!pq.empty()) {
        const auto [dist, cur, fl_free, fl_double] = pq.top(); pq.pop();
        if (dist > dp[cur][fl_free][fl_double]) continue;
        
        for (auto &&e: g[cur]) {
            // 普通に遷移
            if (chmin(dp[e.to][fl_free][fl_double], dp[cur][fl_free][fl_double]+e.cost)) pq.emplace(dp[e.to][fl_free][fl_double], e.to, fl_free, fl_double);

            if (!fl_free) {
                // 無料なので重みは足さない
                if (chmin(dp[e.to][1][fl_double], dp[cur][fl_free][fl_double])) pq.emplace(dp[e.to][1][fl_double], e.to, 1, fl_double);
            }
            if (!fl_double) {
                // 倍の重みを足す
                if (chmin(dp[e.to][fl_free][1], dp[cur][fl_free][fl_double] + e.cost*2)) pq.emplace(dp[e.to][fl_free][1], e.to, fl_free, 1);
            }

            if (!fl_free && !fl_double) {
                // 倍かけて無料にする(今まで通った辺が一つしかない)時、2*w - w = w
                if (chmin(dp[e.to][1][1], dp[cur][fl_free][fl_double] + e.cost)) pq.emplace(dp[e.to][1][1], e.to, 1, 1);
            }
        }
    }

    for (int i = 1; i < n; ++i) {
        cout << dp[i][1][1] << '\n';
    }

    return 0;
}