第二回全国統一プログラミング王決定戦予選 : D - Shortest Path on a Line

ライブラリ不足でタイムロスした。
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がバグってて手間取った。