Codeforces #179 Div1. B. Greg and Graph

さてB。本番何度か苦戦したけど何とか解けた。
http://codeforces.com/contest/295/problem/B

問題

すべての点同士にコスト付有向辺があるN点からなるグラフが与えられる。
ここで、N回以下の処理を行う。

• i番目に取り除く点の番号が与えられるので、その点およびその点に出入りする辺をすべて取り除く。
• 残された点について、各２点の組ごとに最短経路のコストの和の最小値を求めて、その値を出力せよ。

解法

だんだん減らす、と考えると難しいがこれは逆順に考えればだんだん点が増えていくことになる。
よって、逆に点を増やしつつFloyd法を実行して行けば、O(N^3)で処理できる。

最短経路を更新する順序を気を付けていかないと危ないね。

int N;
ll co[501][501];
ll res[501];
vector<int> V;
int fin[501];

void solve() {
	int f,r,i,j,k,l,x,y;
	ll t;
	
	N=GETi();
	FOR(x,N) FOR(y,N) co[x][y]=GETi();
	FOR(x,N) V.push_back(GETi()-1);
	reverse(V.begin(),V.end());
	
	ll su=0;
	FOR(i,N) {
		FOR(x,i+1) FOR(y,i+1) co[V[x]][V[i]] = min(co[V[x]][V[i]], co[V[x]][V[y]]+co[V[y]][V[i]]);
		FOR(x,i+1) FOR(y,i+1) co[V[i]][V[x]] = min(co[V[i]][V[x]], co[V[i]][V[y]]+co[V[y]][V[x]]);
		FOR(x,i+1) FOR(y,i+1) co[V[x]][V[y]] = min(co[V[x]][V[y]], co[V[x]][V[i]]+co[V[i]][V[y]]);
		
		FOR(x,i+1) FOR(y,i+1) res[N-1-i]+=co[V[x]][V[y]];
	}
	
	FOR(i,N) {
		if(i!=0) cout << " ";
		cout << res[i];
	}
	cout << endl;
	
	return;
}

まとめ

「これFloydの逆じゃない？」と気づいたらすぐ回答できた。
まぁ最小コストの更新順を間違えて何度かWrong Answer出してしまったけど。