Codeforces #287 Div2 E. Breaking Good

やっぱりDより楽な気がする。
http://codeforces.com/contest/507/problem/E

問題

N頂点M無向辺からなる連結グラフが与えられる。
各辺は破損している場合があり、修理の要否も入力として与えられる。

ここで1番の頂点からN番の頂点まで移動したい。
以下の条件を満たすように辺を破壊or修理する数を最小化し、対象の辺を答えよ。

• 1番の頂点からN番の頂点までの移動経路は最短路である。
• 移動経路はすべて非破損、その他の辺はすべて破損状態にする。

解法

基本的な考え方は以下の通り。

• まずBFSで最短路候補を求める。
• 破壊・修理数を最小にするには、最短路のうち破損辺を少なく通るようにすればよい。よって最短路群を再度ダイクストラ法で探索して通る破損辺を最小化する。

ダイクストラ法の結果をバックトラックすれば通る辺が確定するので、通る辺の破損辺を修理しつつ通らない辺の非破損辺を破壊すればよい。

なお、上記処理は２回探索を行うし、自分も本番ではそう解いたが、１回の探索で済ませる方法もある。
移動経路における移動距離の大小は破損辺の数の大小より優先されるので、コストとして(移動距離*100000+破損辺の数)を考えて１回ダイクストラ法を行うだけでも良い。

int N,M;
vector<pair<int,int> > E[101000];
int X[101000],Y[101000],Z[101000];
int dist[100100];
int cost[100100];
int from[100100];
int un[100100],ret;
map<pair<int,int>,int> MM;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>X[i]>>Y[i]>>Z[i];
		X[i]--;Y[i]--;
		E[X[i]].push_back(make_pair(Y[i],i));
		E[Y[i]].push_back(make_pair(X[i],i));
		MM[make_pair(X[i],Y[i])]=MM[make_pair(Y[i],X[i])]=i;
	}
	FOR(i,N) dist[i]=cost[i]=5<<20;
	
	priority_queue<pair<ll,int> > Q;
	dist[0]=cost[0]=0;
	Q.push(make_pair(0,0));
	while(Q.size()) {
		int cur=Q.top().second;
		Q.pop();
		FOR(i,E[cur].size()) {
			int tar=E[cur][i].first;
			if(dist[tar]>dist[cur]+1 ||
			   (dist[tar]==dist[cur]+1 && cost[tar]>cost[cur]+(Z[E[cur][i].second]^1))) {
				dist[tar]=dist[cur]+1;
				cost[tar]=cost[cur]+(Z[E[cur][i].second]^1);
				from[tar]=cur;
				Q.push(make_pair(-dist[tar]*10000000LL-cost[tar],tar));
			}
		}
	}
	
	x=N-1;
	while(x!=0) {
		y=MM[make_pair(x,from[x])];
		if(Z[y]==0) un[y]=2,ret++;
		else un[y]=1;
		x=from[x];
	}
	FOR(i,M) if(un[i]==0 && Z[i]==1) un[i]=2,ret++;
	_P("%d\n",ret);
	FOR(i,M) if(un[i]==2) _P("%d %d %d\n",X[i]+1,Y[i]+1,Z[i]^1);
}

まとめ

解法は割とすぐ思いついたけど、２回探索の解法でコーディングに時間かかってしまった。