AtCoder ARC #090 : E - Avoiding Collision

ちょっと無駄があったけどまぁそこそこの順位。
https://beta.atcoder.jp/contests/arc090/tasks/arc090_c

問題

移動時間の設定された辺をもつ無向グラフがある。
2頂点S,Tが与えられたとき、2人はS,TからそれぞれT,Sに最短路のいずれかを用いて移動しようとする。
この時、両者がぶつからない経路の取り方は何通りあるか。

解法

S,Tそれぞれを始点としたダイクストラ法を実行し、各頂点以下を求めよう。

• S,Tからの最短距離
• その最短距離で到達する経路の組み合わせ

「ぶつからない」の部分を除けば、S→Tに至る最短経路数の2乗分の組み合わせがある。
ここからぶつかる経路を除こう。

両者がぶつかるのは以下のいずれか。

• S,Tの最短経路上にある頂点で、両者への距離が近い頂点vを両者が選択する場合。
• S,Tの最短経路上にある辺U-Vで、UがS寄り、VがT寄りにある場合、両者がその間の辺を用いる場合。

前者は((S-Vの経路)^2*(V-Tの経路)^2)、後者は((S-Uの経路)^2*(V-Tの経路)^2)分だけぶつかるケースを生じるので、その分取り除こう。

int N,M;
int S,T;
vector<pair<int,int>> E[101010];
ll D[2][101010];
ll pat[2][101010];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>S>>T;
	S--,T--;
	FOR(i,M) {
		cin>>x>>y>>j;
		x--,y--;
		E[x].push_back({y,j});
		E[y].push_back({x,j});
	}
	
	priority_queue<pair<ll,int>> P;
	pat[0][S]=pat[1][T]=1;
	FOR(i,N) D[0][i]=D[1][i]=1LL<<60;
	D[0][S]=D[1][T]=0;
	P.push({0,S});
	P.push({0,100000+T});
	
	while(P.size()) {
		int cur=P.top().second%100000;
		int id=P.top().second/100000;
		ll co=-P.top().first;
		P.pop();
		if(D[id][cur]!=co) continue;
		FORR(e,E[cur]) {
			if(co+e.second < D[id][e.first]) {
				pat[id][e.first]=0;
				D[id][e.first] = co+e.second;
				P.push({-D[id][e.first],id*100000+e.first});
			}
			if(co+e.second == D[id][e.first]) (pat[id][e.first]+=pat[id][cur])%=mo;
			
		}
	}
	
	
	ll tot=pat[0][T]*pat[0][T]%mo;
	FOR(i,N) if(D[0][i]+D[1][i]==D[0][T]) {
		if(D[0][i]==D[1][i]) {
			tot+=mo-pat[0][i]*pat[0][i]%mo*pat[1][i]%mo*pat[1][i]%mo;
		}
		if(D[0][i]<D[1][i]) {
			FORR(e,E[i]) if(D[0][e.first]+D[1][e.first]==D[0][T] && D[0][e.first]>D[1][e.first] && D[0][e.first]==D[0][i]+e.second) {
				tot+=mo-pat[0][i]*pat[0][i]%mo*pat[1][e.first]%mo*pat[1][e.first]%mo;
			}
		}
		tot%=mo;
		
	}
	
	cout<<tot<<endl;
}

まとめ

FよりE手間取ったのもったいない。