TopCoder SRM 679 Div2 Hard ForbiddenStreets

似た問題Codeforcesで見たことあるけど、どれだったかな…。
https://community.topcoder.com/stat?c=problem_statement&pm=14121

問題

N頂点M距離付無向辺で構成される連結グラフが与えられる。
各辺に対し、「その辺が無かったら、あったときに比べ最短距離が長くなる頂点対の数」を求めよ。

解法

Nはさほど大きくないので、頂点対及び辺を総当たりし、O(N^2*M)掛けても間に合う。
あとは頂点対と辺に対し「その辺がなくなると頂点対の最短距離が長くなる」かどうかを高速に判定する方法を考えよう。

まず各頂点を始点としてそれぞれダイクストラ法を行い、頂点対a→bに対し、最短距離と経路の組み合わせ数を求めよう。
この経路の組み合わせ数は大きな整数の剰余でも良いが、Challengeで容易に狙った組み合わせの数のグラフを構築できるため、複数の値の剰余を持っておく方が良い。

あとは頂点対x→yに対し、辺p→qが題意を満たす辺かどうかを判定しよう。
まずp→qが最短経路上にあるためには、x→yの最短距離とx→p→q→yの最短距離が一致しなければならない。
また、p→qが最短経路上で必ず通らなければいけない辺であるためには、x→yの最短移動経路の組み合わせ数が、x→pとq→yの組み合わせの積であればよい。

vector<pair<int,int> > E[101];
ll dist[101][101];
ll pat[2][101][101];
ll mo[2]={1000000007,1000000009};

class ForbiddenStreets {
	public:
	vector <int> find(int N, vector <int> A, vector <int> B, vector <int> time) {
		int i,j,x,y;
		
		FOR(x,N) E[x].clear();
		FOR(x,A.size()) E[A[x]].push_back({B[x],time[x]});
		FOR(x,A.size()) E[B[x]].push_back({A[x],time[x]});
		
		FOR(x,N) FOR(y,N) dist[x][y]=10000000;
		priority_queue<pair<int,int>> Q;
		FOR(x,N) dist[x][x]=0,pat[0][x][x]=pat[1][x][x]=1, Q.push({0,x*100+x});
			
		while(Q.size()) {
			auto q=Q.top();
			Q.pop();
			
			int co=-q.first;
			int st=q.second%100;
			int cur=q.second/100;
			if(dist[st][cur]!=co) continue;
			FORR(r,E[cur]) {
				if(dist[st][r.first]>co+r.second) {
					dist[st][r.first]=co+r.second;
					Q.push({-dist[st][r.first],st*100+r.first});
					pat[0][st][r.first]=pat[1][st][r.first]=0;
				}
				if(dist[st][r.first]==co+r.second) {
					(pat[0][st][r.first]+=pat[0][st][cur])%=mo[0];
					(pat[1][st][r.first]+=pat[1][st][cur])%=mo[1];
				}
			}
		}
		
		vector<int> V(A.size());
		FOR(i,A.size()) {
			int a=A[i],b=B[i];
			FOR(x,N) FOR(y,N) if(dist[x][a]+time[i]+dist[y][b]==dist[x][y]) {
				if(pat[0][x][y]==pat[0][x][a]*pat[0][b][y]%mo[0]&&
				   pat[1][x][y]==pat[1][x][a]*pat[1][b][y]%mo[1])
				   	V[i]++;
			}
		}
		return V;
	}
}

まとめ

本番mod 10^9+7は狙い撃ちされなかったのかな？