kmjp's blog

競技プログラミング参加記です

AtCoder ARC #035 : C - アットコーダー王国の交通事情

解法はすぐ思いついたが、配列添え字のミスを繰り返し無駄タイムロス。
http://arc035.contest.atcoder.jp/tasks/arc035_c

問題

距離付無向辺の連結グラフが与えられる。
i番とj番の頂点の最短距離をD(i,j)とするとき、Sを全頂点対(i,j)におけるD(i,j)の総和とする。

ここでK個のクエリが与えられる。
各クエリではx番とy番の頂点の間に距離zの辺を追加する。
その都度Sを答えよ。

解法

まずWarshall-Floyedで全頂点間の距離及びSを求める。

次に各クエリを処理する。
x・y間の距離がzになることにより、頂点対(i,j)に対し、i→x→y→jまたはi→y→x→jの経路をたどることで距離が短くなる可能性がある。
よってD(i,j)=min(D(i,j), D(i,x)+z+D(y,j), D(i,y)+z+D(x,j))で更新し、同時にSも更新していけば良い。

以下では実装を簡単にするためにSをi,jの大小関係問わずD(i,j)の和として計算し、答えの出力時に2で割っている。

int N,M,K;
ll mat[500][500];
ll tot;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) mat[x][y]=1LL<<40;
	FOR(i,N) mat[i][i]=0;
	FOR(i,M) {
		cin>>x>>y>>r;
		mat[x-1][y-1]=mat[y-1][x-1]=min(mat[y-1][x-1],(ll)r);
	}
	FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
	FOR(y,N) FOR(x,N) tot+=mat[x][y];
	
	cin>>K;
	while(K--) {
		cin>>x>>y>>r;
		x--,y--;
		if(x>y) swap(x,y);
		FOR(i,N) FOR(j,N) {
			if(mat[i][j]>mat[i][x]+r+mat[y][j]) {
				tot -=mat[i][j]-(mat[i][x]+r+mat[y][j]);
				mat[i][j]=(mat[i][x]+r+mat[y][j]);
			}
			if(mat[i][j]>mat[i][y]+r+mat[x][j]) {
				tot -=mat[i][j]-(mat[i][y]+r+mat[x][j]);
				mat[i][j]=(mat[i][y]+r+mat[x][j]);
			}
		}
		
		cout<<tot/2<<endl;
	}
}

まとめ

最初Sを問題通りi<jであるD(i,j)の総和としたために配列indexミスを色々やらかした。