Codeforces #303 Div2 E. Paths and Trees

Div1B位の難易度かなぁ。
http://codeforces.com/contest/545/problem/E

問題

N頂点M重み付無向辺の連結グラフがある。

このグラフからいくつか辺を取り除いたグラフを考える。
取り除く前後で、頂点Uから他の各頂点までの最短コストが同一のうち、残った辺の重さの総和が最小となるようなものを求めよ。

解法

まず各頂点への到達最小コストを求めるため、ダイクストラ法で順次処理していく。
その際、各頂点でどの頂点から到達するのが一番小さいコストの辺で到達できるかを求め、それらを答えに追加していくだけ。

int N,M,S;
int U[303000],V[303000],W[303000];
int ME[303000],MW[303000];
ll dist[303000];
vector<pair<int,int> > E[303000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--,V[i]--;
		E[U[i]].emplace_back(V[i],i);
		E[V[i]].emplace_back(U[i],i);
	}
	
	cin>>S;
	FOR(i,N) dist[i]=1LL<<60;
	dist[--S]=0;
	
	priority_queue<pair<ll,int> > Q;
	Q.push(make_pair(0,S));
	
	ll tot=0;
	while(Q.size()) {
		auto rf=Q.top();
		Q.pop();
		x=rf.second;
		if(dist[x]!=-rf.first) continue;
		
		tot+=MW[x];
		
		FORR(r,E[x]) if(dist[r.first]>=dist[x]+W[r.second]) {
			if(dist[r.first]>dist[x]+W[r.second]) {
				dist[r.first]=dist[x]+W[r.second];
				Q.push(make_pair(-dist[r.first],r.first));
			}
			MW[r.first]=W[r.second];
			ME[r.first]=r.second+1;
		}
	}
	
	cout<<tot<<endl;
	FOR(i,N) if(ME[i]) cout<<ME[i]<<" ";
	cout<<endl;
}

まとめ

これがDiv2 Dでちょうどいいぐらいだと思うんだけどな。