Codeforces Round #25 (Div 2 only) C. Roads in Berland

問題概要

n個の都市が双方向に通行可能な道路で結ばれている。
全ての2都市間の最短距離が与えられる。

ここに、k本の道路を新たに作る。
道路を一本作るたびに、全ての二つの都市の組の間の最短距離の和を出力せよ。

n,k≦300を満たす。
かつ、全ての距離は1から1000の整数である。

解法

k回Warshall-Floydを繰り返すと明らかにTLE.
a-bに新たに道路を作ったとき、最短距離の更新され方はi-a-b-jまたはi-b-a-jしかないことに注目すれる。
すると、最短距離の更新はO(n^2)でできるので間に合う。

都市の最短距離の和はlong longを使わなくても大丈夫だと思ってたんだけど、ダメなよう。
n^2は9万で、道の長さは最大1000だから、和は9000万以下のはずなのに。本番はそれではまった。ちょっと理由がわからない。

ソースコード

int n,d[300][300],K;

void run()
{
	cin>>n;
	rep(i,n)rep(j,n)
	{
		cin>>d[i][j];
		d[j][i]=d[i][j];
	}
	cin>>K;
	rep(it,K)
	{
		int a,b,c;
		cin>>a>>b>>c; a--,b--;
		d[a][b]=d[b][a]=min(d[a][b],c);
		
		
		ll sum=0;
		rep(i,n)
		{
			d[i][a]=d[a][i]=min(d[i][a],d[i][b]+c);
			d[i][b]=d[b][i]=min(d[i][b],d[i][b]+c);
		}
		rep(i,n)rep(j,n)d[i][j]=min(d[i][j],min(d[i][a]+c+d[b][j],d[i][b]+c+d[a][j]));
		
		
		rep(i,n)rep(j,i)sum+=d[i][j];
		cout<<sum<<(it==K-1?"\n":" ");
	}
}