Codeforces #800 : Div1 C. Keshi in Search of AmShZ

コードは短め。
https://codeforces.com/contest/1693/problem/C

問題

N頂点の有向辺からなるグラフが与えられる。
1番の頂点にある駒を、N番の頂点に移動したい。

1手ごとに、以下のいずれかを行える。

• 1つ使用不可な辺を定める
• 駒を今いる点から、使用不可な点を除いて等確率でいずれかの辺の先に移動する。

最適な手順を取るとき、最小何手で駒をN番の頂点に移動できるか。

解法

N番の頂点から、辺を逆向きにたどる形でN番の頂点に至るまでの手数を定めよう。
各点について、遷移先の点のうち、1手かけて辺をつぶしても元が取れるような遷移先への辺をつぶしていくようにすればよい。

int N,M;
vector<int> E[202020],RE[202020];
int in[202020];
int D[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		
		E[x].push_back(y);
		RE[y].push_back(x);
		in[x]++;
	}
	FOR(i,N) D[i]=1<<30;
	D[N-1]=0;
	priority_queue<pair<int,int>> Q;
	Q.push({0,N-1});
	while(Q.size()) {
		int co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(D[cur]!=co) continue;
		FORR(e,RE[cur]) {
			in[e]--;
			if(D[e]>D[cur]+1+in[e]) {
				D[e]=D[cur]+1+in[e];
				Q.push({-D[e],e});
			}
		}
		
	}
	cout<<D[0]<<endl;
}

まとめ

Div1 Cにしてはシンプル。