https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d
前提知識
解説
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; }