Codeforces #709 Div1 : D. Useful Edges

コードは短い。
https://codeforces.com/contest/1483/problem/D

問題

重み付き無向辺を持つN点の無向グラフが与えられる。
また、いくつかのタプル(U[i],V[i],L[i])が与えられる。

各辺eが有効であるとは、以下を意味する。

• いずれかのタプルにおいて、U[i]からV[i]に至るパスのうち、eを通りつつパスの重みの総和がL[i]以下であるようなタプルがある。

グラフ中有効な辺は何通りか。

解法

まずWarshall-Floydの要領で頂点間の最短距離を列挙しておく。
あとは各辺・各タプルについて条件を満たすか判定しようとすると、辺がO(N^2)通り、タプルがO(N^2)通りあるので、総当たりだとO(N^4)かかり間に合わない。
そこでなんとか計算量を減らそう。

タプルのうち、Vが等しいものをまとめて処理することを考える。
すなわち、(U[i],V,L[i])という一連のタプルを考える。
点A-Bをつなぐ重みWの辺が有効か判定することを考えると、D(A,U[i])+W+D(V,B)≦L[i]なら良いわけだが、式変形すると-L[i]+D(U[i],B)≦-W-D(V,A)となる。

Bに対し全タプルを総当たりすれば、全B,Vに対する左辺の最小値をO(N^3)で列挙できる。
あとは、(A,B,W)の対に対し、Vを総当たりすればこちらも辺がO(N^2)通りでVの総当たりがO(N)通りなので、全体でO(N^3)で処理できる。

int N,M,Q;
int U[404040],V[404040],W[404040];
vector<pair<int,int>> E[404040];
ll dp[606][606];
ll S[606][606];
ll C[606][606];
ll D[660];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) S[x][y]=dp[x][y]=(x==y)?0:1LL<<60;
	FOR(x,N) S[x][x]=1LL<<60;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--,V[i]--;
		dp[U[i]][V[i]]=dp[V[i]][U[i]]=W[i];
		S[U[i]][V[i]]=S[V[i]][U[i]]=W[i];
	}
	FOR(k,N) FOR(x,N) FOR(y,N) dp[x][y]=min(dp[x][y],dp[x][k]+dp[k][y]);
	
	FOR(x,N) FOR(y,N) C[x][y]=-1;
	cin>>Q;
	FOR(i,Q) {
		cin>>x>>y>>k;
		C[x-1][y-1]=C[y-1][x-1]=k;
	}
	
	int num=0;
	FOR(i,N) FOR(y,N) {
		ll ma=-1;
		FOR(j,N) ma=max(ma,C[i][j]-dp[y][j]);
		FOR(x,N) if(S[x][y]+dp[i][x]<=ma) {
			num++;
			S[x][y]=S[y][x]=1LL<<60;
		}
	}
	
	cout<<num<<endl;
}

まとめ

言われてみれば、そうだし単純なんだけど、これをさっと求めるのは難しい。