Codeforces #625 Div1 B. Navigation System

問題文が長い…。
https://codeforces.com/contest/1320/problem/B

問題

有向グラフが与えられる。
今このグラフを辺にそって点S→Tに移動するとする。

その際、ナビを使う。ナビは現在位置から目的地への最短ルートを一つ示す。
ただし複数ルートがある場合、どれを示すかは不定である。
またナビの示すルートを無視して移動した場合、最短ルートの再計算が行われる。

ここで一つの移動経路が与えられる。
これに沿って移動する場合、再計算の回数の最小値・最大値を求めよ。

解法

まず目的地から逆向きにDFSして、各点から目的地までの最短距離を求める。
次に、各点においてナビが示す次の点の候補が何通りあるか求めよう。
これは自身の点より、目的地までの距離が1つ小さい点が何個隣接しているかを調べればよい。

この上で、移動経路にそって移動したとき、各点について以下を行う。

• 次の点が最短経路としての候補にないなら、必ず再計算が起こるので最大値・最小値ともにインクリメントする。
• 次の点が最短経路としての候補にある場合、他に候補があるなら最大値のみインクリメントする。

int N,M;
vector<int> E[202020];
vector<int> RE[202020];
vector<int> ne[202020];
int D[202020],mi[202020];
int K;
vector<int> P;
int cand[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		RE[y-1].push_back(x-1);
	}
	FOR(i,N) D[i]=202020;
	
	cin>>K;
	FOR(i,K) cin>>x, P.push_back(x-1);
	D[P.back()]=0;
	queue<int> Q;
	Q.push(P.back());
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		FORR(e,RE[cur]) if(D[e]>D[cur]+1) {
			D[e]=D[cur]+1;
			Q.push(e);
		}
	}
	
	FOR(i,N) {
		mi[i]=202020;
		FORR(e,E[i]) mi[i]=min(mi[i],D[e]);
		FORR(e,E[i]) cand[i]+=D[e]==mi[i];
	}
	
	int L=0,R=0;
	FOR(i,P.size()-1) {
		if(D[P[i+1]]==mi[P[i]]) {
			if(cand[P[i]]>1) R++;
		}
		else {
			L++;
			R++;
		}
	}
	cout<<L<<" "<<R<<endl;
	
	
}

まとめ

もうちょい短い問題文だといいんだけどな。