95 C Volleyball

問題

n個の交差点がm本の双方向に通行可能な道路によって結ばれている。
m本の道路は、
始点s[i],終点t[i],距離w[i]の形式で与えられる。

各交差点にはタクシーがいて、利用料金は距離にかかわらずc[i]、ただし利用距離の限度はそれぞれt[i]である。

このとき、交差点xからyへ移動するのに必要な金額の最小値を求めよ。
移動が不可能である場合-1を出力せよ。

制約条件

n,m≦1000
wi≦10^9
ti,ci≦10^9

方針

まずは全点間の最短距離を求めたい。
が、ワーシャルフロイドをすると多分1000^3なのでTLE.
グラフが疎なのでDijkstra法を各頂点から行う。

全点間最短距離が求まったら、始点から料金でDijkstra法を行う。
（グラフは、距離がt[i]以下のときに移動できる、すなわち重みc[i]の枝があるとする）

以下のソースで二回目のDijkstra法はpriority_queueを使わない実装をしている。
（priority_queueを使うとO(E log V)で、使わないとO(V^2)。ここでは辺はV^2本なので、使わない実装のほうが高速なのでそっちにしてある。多分どっちでも通るけど）

ソースコード

int n,m; ll t[1000],c[1000];
ll d[1000][1000], cost[1000];
vector<vector<pi> >e;

void run(){
	cin>>n>>m;
	int x,y; cin>>x>>y; x--; y--;
	
	e.clear(); e.resize(n);
	rep(i,m){
		int s,t,c; cin>>s>>t>>c;
		s--; t--;
		e[s].pb(mp(t,c)); e[t].pb(mp(s,c));
	}
	rep(i,n)cin>>t[i]>>c[i];
	
	rep(i,n)rep(j,n)d[i][j]=1e12;
	rep(i,n){
		d[i][i]=0;
		priority_queue<pair<ll,int> >q;
		q.push(mp(0,i));
		while(!q.empty()){
			int c=q.top().second; ll cc=q.top().first;
			q.pop();
			if(d[i][c]<-cc)continue;
			
			rep(j,e[c].size())if(d[i][e[c][j].first]>-cc+e[c][j].second)
			q.push(mp(cc-e[c][j].second,e[c][j].first)),
			d[i][e[c][j].first]=-cc+e[c][j].second;
		}
	}

	bool v[1000]={};
	rep(i,n)cost[i]=1e12; cost[x]=0;
	rep(i,n){
		ll mn=1e12; int mni=-1;
		rep(j,n)if(!v[j]&&mn>cost[j])mni=j, mn=cost[j];
		if(mni==-1)break;
		v[mni]=1;
		
		rep(j,n)if(d[mni][j]<=t[mni]&&cost[j]>mn+c[mni])cost[j]=mn+c[mni];
	}
	cout<<(cost[y]==1e12?-1:cost[y])<<endl;
}