ライブラリ不足でタイムロスした。
https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d
問題
1~NのN頂点からなる有向グラフを考える。
このグラフに、以下のように辺を張る。
- パラメータ[L,R,C]が与えられたとき、L≦s<t≦Rであるs→tに、コストCの辺を張る
1番の頂点からN番の頂点に至る最小コストを求めよ。
解法
D(v) := 1番の頂点からv番の頂点に至る最小コスト
とすると、D(v)≦D(v+1)が成り立つ。ここから以下のことがわかる。
- [L,R,C]のパラメータで表せる辺を使うなら、頂点Lから使う場合だけ考えればよい。
その場合、区間[L+1,R]にはD(L)+Cで移動できる。
そこでmultiset等使いその値の一覧とその最小値を保持し、D(v)を順に求めよう。
区間更新可能なRMQが処理できるSegTreeで解いてもよい。
int N,M; vector<pair<int,int>> add[101010]; vector<ll> del[101010]; ll dp[101010]; multiset<ll> D; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y>>r; add[x].push_back({y,r}); } D.insert(0); del[1].push_back(0); for(i=1;i<=N;i++) { if(D.empty()) return _P("-1\n"); dp[i]=*D.begin(); FORR(a,del[i]) D.erase(D.find(a)); FORR(a,add[i]) { D.insert(dp[i]+a.second); del[a.first].push_back(dp[i]+a.second); } } cout<<dp[N]<<endl; }
まとめ
なんか手持ちのSegTreeがバグってて手間取った。