D - Shortest Path on a Line

問題

atcoder.jp

考えたこと

・愚直に辺をつなぐと間違いなくTLE. 辺を追加するクエリを頂点とみなすか、実は全部辺を考慮する必要がないかのどちらかだと思った。
・任意のの2頂点間はで接続することができる。
・したがって、「辺を追加する」という区間とコストを辞書順かつ昇順にソート済みのクエリについて、以下のように言い換えることができる。

番目のQueryに対し、]について
頂点1からのの最短距離をとする。
に更新する。ただし、は区間内の最小値で、
] を満たす。

・必要になるデータ構造は、区間の最小値取得 + 区間を最小値で更新
・SegmentTreeBeatsというらしいです。すごい。コピーしてきてAC。

想定解

想定解のほうが鮮やか(当社比)なのでそれも書きます
・実はすべてのの辺について考える必要はなく、隣接する2頂点間をコスト0で結ぶ辺と,を考えるとよい。
・無向辺で接続すると、最短経路問題に帰着できない・・・辺に関わらず出力が常に0になる。
・隣接する２頂点の辺の張り方を工夫する。具体的にはからの有向辺を貼る。すると,をうまくすべての区間に伝搬することができる。
・具体的に考える。まず頂点1のコストは0であり、これは明らかに最短経路である。]を満たすQueryのうち,が最小のものをとする。
・頂点1の最短経路はすでに求まっているため、]内の最短経路は間違いなくまたは0 になる。
・↑を繰り返すと求まる。これはDIjkstra法と同じ。おそらく、このグラフの最短経路は1に近い方から順に求まっていく。したがって、Queryの区間内に最小値が存在することは無い(多分)
・間違ってそう。問題があればリプください。

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
    Int N,M;
    cin >> N >> M;
    using tp = tuple<Int,Int>;
    vector<vector<tp>>edge(N);
    for(Int v = 0; v + 1 < N; ++v){
        edge[v + 1].emplace_back(v,0LL);
    }
    for(int i = 0; i < M; ++i){
        Int u,v,c;
        cin >> u >> v >> c; --u; --v;
        edge[u].emplace_back(v,c);
    }
    constexpr Int inf = (1LL << 60);
    vector<Int>d(N,inf);

    priority_queue<tp,vector<tp>,greater<>>que;
    que.emplace(0,0);
    d[0] = 0;
    while(not que.empty()) {
        auto p = que.top(); que.pop();
        Int crt,v;
        tie(crt,v) = p;
        if(crt > d[v]) continue;
        for(auto tup : edge[v]){
            Int nv,cost;
            tie(nv,cost) = tup;
            if(cost + crt >= d[nv]) continue;
            d[nv] = cost + crt;
            que.emplace(d[nv],nv);
        }
    }
    cout << (d.back() == inf ? -1 : d.back()) << endl;
}