Shortest Path on a Line [NIKKEI Programming Contest 2019-2 D]

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d

前提知識

• セグメントツリーによるDP高速化

解説

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8371669

本家解答はダイクストラ。
以下、セグメントツリーとDPによる解答を示す。

区間条件と最短経路といえば、Rを昇順に処理していって、DPをセグメントツリーで高速化テク。
この方針で考えていくと解けそうになってくる。
dp[i] := 頂点iに到着する為の最短経路
区間をR昇順でソートして、順番にDPを更新していく。
dp[R] = min(dp[R], min(dp[L], dp[L+1], ..., dp[R]) + C)
これで更新していけばいい。

更新先が頂点Rだけで良い理由を説明する。
区間[L1,R1]を使って移動した後に、区間[L2,R2]を使って移動するためには、
[L2,R2]の中にR1が入っているかだけを考えればいい。
よって、区間[L1,R1]を使って移動してきたという情報を頂点R1だけに伝播させれば、
直前の移動情報を正しく、かつ、まとめて保持しておくことができる。
それっぽく説明したけど、後付なので謎理論かも。

あとは、dp[N]が答え。

int N, M;
vector<pair<int, int>> Q[101010];
SegTree<ll, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int l, r, c; cin >> l >> r >> c;
        Q[r].push_back({ l, c });
    }

    st.update(1, 0);
    rep(r, 1, N + 1) {
        fore(p, Q[r]) {
            int l = p.first;
            int c = p.second;
            st.update(r, min(st[r], st.get(l, r) + c));
        }
    }
    ll ans = st[N];
    if (ans == infl) ans = -1;
    cout << ans << endl;
}