Codeforces #257 Div1 B. Jzzhu and Cities

こちらも本番しょうもないミスで落とした…。
http://codeforces.com/contest/449/problem/B

問題

N個の都市がM本の両方向の道路があり、それぞれ距離が与えられる。
それとは別に、0番の都市からK個の都市に線路があり、それぞれ距離が与えられる。

0番の都市から各都市に行く最短経路を求める際、元のグラフと最短経路の距離が変わらない範囲で、線路をいくつか取っ払いたい。
最大何個の線路を取っ払えるか。

解法

道路と線路を合わせたダイクストラ法を使う。
i番目の都市への距離を考える際、0番→i番の移動手順において、0番→i番の線路1発で移動するのが他の移動経路より距離が短い場合、その線路は使わなければならない。
それ以外の場合その線路は不要である。

int N,M,K;
ll U[400001],V[400001],X[400001];
ll Y[400001];
vector<pair<int,int> > E[400001];
ll D[400001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	FOR(i,N) Y[i]=D[i]=1LL<<60;
	
	FOR(i,M) {
		cin>>U[i]>>V[i]>>x;
		E[U[i]-1].push_back(make_pair(V[i]-1,x));
		E[V[i]-1].push_back(make_pair(U[i]-1,x));
	}
	
	priority_queue<pair<ll,int> > Q;
	FOR(i,K) cin>>x>>y, Y[x-1]=min(Y[x-1],(ll)y);
	FOR(i,N) if(Y[i]!=1LL<<60) Q.push(make_pair(-Y[i],i));
	
	D[0]=0;
	Q.push(make_pair(0,0));
	
	int ret=K;
	while(!Q.empty()) {
		ll cd=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		
		if(cd<D[cur]) ret--,D[cur]=cd;
		if(cd!=D[cur]) continue;
		
		FOR(i,E[cur].size()) {
			int tar=E[cur][i].first;
			ll co=cd+E[cur][i].second;
			if(D[tar]>co) {
				D[tar]=co;
				Q.push(make_pair(-co,tar));
			}
		}
	}
	cout << ret << endl;
	
}

まとめ

本番代入の前後を入れ替えるというしょうもないミスで落とした。