Codeforces #241 Div2 E. President's Path

アプローチが本番に思いついたのはよかったんだけどな。
http://codeforces.com/contest/416/problem/E

問題

N点M辺からなる無向グラフが与えられる。
各辺には長さが与えられる。

N点中の点の対(s,t)それぞれについて、sからtに至る最短経路上に来る可能性のある辺の数を答えよ。

解法

まずWarshall-Floyd法で各点の最短経路を求めておこう。

s->tに至る最短経路において、u->vという辺がその上に乗る可能性があるかどうかはs->uとu->vとv->tの長さの和がs->tの長さと一致するかどうかでわかる。
ただし、辺の数は最大O(N^2)、点の対の選び方がO(N^2)なのでこの方法ではO(N^4)かかりTLEする。

よって以下のようにすることでO(N^3)に押さえることを考える。
まず、a->bに移動する場合、最初の１手でとりうる辺の数E[a][b]を求めよう。
これは各点vにおいてa->v + v->b == a->bとなるvの数を列挙すればよく、O(N^3)。

次にこの辺の数を用いてs->tに至る最短経路の辺の和を求める。
各点wにおいて、s->tに至る最短経路でwを取りうるかどうかは、s->w + w->t == s->tかどうかで判断できる。
wがこの等式を満たすなら、E[w][t]をs->tに至る最短経路上の辺の数に加算すればよい。

int N,M;
ll mat[501][501];
ll mat2[501][501];
ll use[501][501];
ll tot[501][501];
void solve() {
	int f,i,j,k,l,x,y,x2,y2;
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) mat[x][y]=2000000;
	FOR(x,N) mat[x][x]=0;
	FOR(i,M) {
		cin>>x>>y>>l;
		mat[x-1][y-1]=mat[y-1][x-1]=l;
	}
	
	FOR(x,N) FOR(y,N) mat2[x][y]=mat[x][y];
	FOR(l,N) FOR(x,N) FOR(y,N) mat2[x][y]=min(mat2[x][y],mat2[x][l]+mat2[l][y]);
	
	FOR(x,N) FOR(y,N) FOR(l,N) 
		use[x][y] += (x!=y && l!=x && mat[x][l]==mat2[x][l] && mat2[x][l]+mat2[l][y]==mat2[x][y] && mat2[y][x]<2000000);
		
	FOR(x,N) for(y=x+1;y<N;y++) FOR(l,N) if(l!=y && mat2[x][l]+mat2[l][y]==mat2[x][y] && mat2[y][x]<2000000) tot[x][y]+=use[l][y];
	
	FOR(x,N) for(y=x+1;y<N;y++) _P("%lld ",tot[x][y]);
	_P("\n");
	
}

まとめ

アプローチはあっていたので、本番に当てたかったな。