解法はすぐ思いついたが、配列添え字のミスを繰り返し無駄タイムロス。
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ミスを色々やらかした。