AtCoder ABC #375 (パナソニックグループ プログラミングコンテスト2024) : G - Road Blocked 2

想定解じゃなかった。
https://atcoder.jp/contests/abc375/tasks/abc375_g

問題

N点M辺からなる、辺に距離付きの無向グラフが与えられる。
全辺が使える場合に対し、各辺が使えない場合、1番からN番の点への最短距離が変化するかを求めよ。

解法

まず以下を求めておく。
f(a,b) := a番の点からb番の点への最短距離
g(a,b) := a番の点からb番の点への最短距離で至る経路の組み合わせ数

ただし、aは1とNの場合だけ求めておけばよい。

点u,vを結ぶ長さlの辺に対し、使えない場合に最短距離が変化するかを求める。
まず、この辺を使うと最短距離になるかを判定する。
f(1,u)+l+f(N,v) = f(1,N)かf(1,v)+l+f(N,u) = f(1,N)ならよい。

もし、この辺を通らないと最短距離が変化する場合、g(1,u)*g(N,v) != g(1,N)なのでこれを判定すればよい。
以下のコードでは、3つの素数のmodを取ってg(a,b)を計算している。

int N,M;
int A[202020],B[202020],C[202020];
vector<pair<int,int>> E[202020];
ll dp[202020][2],pat[202020][2];
ll same[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		A[i]--,B[i]--;
		E[A[i]].push_back({B[i],C[i]});
		E[B[i]].push_back({A[i],C[i]});
		same[i]=1;
	}
	
	vector<ll> mos={1000000007,1000000009,998244353};
	FORR(mo,mos) {
		FOR(i,N) {
			dp[i][0]=dp[i][1]=1LL<<60;
			pat[i][0]=pat[i][1]=0;
		}
		dp[0][0]=dp[N-1][1]=0;
		pat[0][0]=1;
		pat[N-1][1]=1;
		priority_queue<pair<ll,int>> Q;
		Q.push({0,0});
		Q.push({0,2*N-1});
		while(Q.size()) {
			ll co=-Q.top().first;
			int cur=Q.top().second%N;
			int id=Q.top().second/N;
			Q.pop();
			if(dp[cur][id]!=co) continue;
			FORR2(e,c,E[cur]) {
				int up=0;
				if(chmin(dp[e][id],co+c)) pat[e][id]=0, up=1;
				if(dp[e][id]==co+c) (pat[e][id]+=pat[cur][id])%=mo;
				if(up) Q.push({-dp[e][id],id*N+e});
			}
		}
		ll mi=dp[N-1][0];
		FOR(i,M) {
			if(mi==dp[A[i]][0]+C[i]+dp[B[i]][1]) {
				if(pat[N-1][0]==pat[A[i]][0]*pat[B[i]][1]%mo) same[i]=0;
			}
			if(mi==dp[A[i]][1]+C[i]+dp[B[i]][0]) {
				if(pat[N-1][0]==pat[B[i]][0]*pat[A[i]][1]%mo) same[i]=0;
			}
		}
	}
	FOR(i,M) {
		if(same[i]) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	
		
}

まとめ

本番中に橋は考えなかったな…。