Codeforces 141 D. Take-off Ramps

問題

長さLのスキーのコースがある。
n個のジャンプ台があり、それぞれの座標はx[i]
ジャンプ台を使うと、x[i]+d[i]に、t[i]の時間をかけて飛ぶことができる。
ただし、ジャンプ台を使うためにはx[i]-p[i]から地上を滑っている必要がある。

スキーヤーが地上をすべるスピードは1であるとき、
コースを滑り終えるのにかかる最短時間を求めよ。

コースは逆走してもよいが、ジャンプはゴール方向へとしか飛べない。
また、コースの外にはみ出てはならない。

制約条件

n≦10^5
L≦10^9

方針

単なるDijkstra+経路復元（+座標圧縮）。
Dijkstraとか久々すぎて存在が頭の中から消えていた。

費用流のときは毎回書いているはずなのに。
経路復元をするので、ノードに、直前のノードの情報を持たせる。
逆走できることを忘れずに。

ソースコード

const int MX=200002;
int v[MX],m,prev[MX],prevjump[MX];
vi jump[MX];

void run()
{
	int n,L; cin>>n>>L;
	vi x(n),d(n),t(n),p(n);
	
	m=0;
	rep(i,n){
		cin>>x[i]>>d[i]>>t[i]>>p[i];
		if(x[i]-p[i]>=0)v[m++]=x[i]-p[i];
		v[m++]=x[i]+d[i];
	}
	v[m++]=0; v[m++]=L;
	
	sort(v,v+m);
	m=unique(v,v+m)-v;
	
	rep(i,n)if(x[i]-p[i]>=0){
		int pos=lower_bound(v,v+m,x[i]-p[i])-v;
		jump[pos].pb(i);
	}
	
	rep(i,m)prev[i]=prevjump[i]=-1;
	
	priority_queue<pair<pi,pi> > q;
	q.push(mp(mp(0,0),mp(-1,-1)));
	while(!q.empty()){
		int c=q.top().first.second, cost=q.top().first.first;
		int prv=q.top().second.first, pj=q.top().second.second;
		q.pop();
		if(prev[c]>=0)continue;
		prev[c]=prv;
		prevjump[c]=pj;
		
		if(c==m-1){
			cout<<-cost<<endl;
			break;
		}
		
		rep(i,jump[c].size()){
			int id=jump[c][i], dist=p[id]+t[id];
			int pos=lower_bound(v,v+m,x[id]+d[id])-v;
			if(prev[pos]<0)q.push(mp(mp(cost-dist,pos),mp(c,id)));
		}
		if(c<m-1)q.push(mp(mp(cost-(v[c+1]-v[c]),c+1),mp(c,-1)));
		if(c&&prev[c-1]<0)q.push(mp(mp(cost-(v[c]-v[c-1]),c-1),mp(c,-1)));
	}
	int i=m-1;
	vi ans;
	while(i!=0){
		if(prevjump[i]>=0)ans.pb(prevjump[i]+1);
		i=prev[i];
	}
	reverse(all(ans));
	cout<<ans.size()<<endl;
	rep(i,ans.size())cout<<ans[i]<<(i==ans.size()-1?"\n":" ")<<endl;
}