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

問題

問題概要

省略

解法

まず、ワーシャルフロイドで、任意の２点間の最短距離を計算しておく。そのあとは、辺が一つ追加されるだけなので、追加される辺が、x-yであれば、任意の２点間の最短距離は、i -> j = i -> x -> y -> j = i -> y -> x -> j のなかで最小のものを選ぶことで更新することができる。

ミス

オーバーフローしていることに気が付けなくて苦労した。

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9 + 1;

//dist[i][j] := iからjまでの最短距離
int dist[410][410];
signed main(void){
    int n, m; cin >> n >> m;

    rep(i, 401)rep(j, 401){
        dist[i][j] = INF;       
    }
    rep(i, 401) dist[i][i] = 0;

    for (int i = 0; i < m; ++i)
    {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        dist[a][b] = min(dist[a][b], c);
        dist[b][a] = min(dist[b][a], c);
    }

    // floyd
    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int time; cin >> time;
    //辺を更新していく
    for (int t = 0; t < time; ++t)
    {
        int x, y, z; cin >> x >> y >> z;
        x--; y--;
        dist[x][y] = min(dist[x][y], z);
        dist[y][x] = min(dist[y][x], z);

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                //i -> j  = i -> x -> y -> j = i -> y -> x -> j
                dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][y] + dist[y][j]);
                dist[i][j] = min(dist[i][j], dist[i][y] + dist[y][x] + dist[x][j]);
            }
        }
        
        ll ret = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                ret += dist[i][j];
            }
        }
        cout << ret << endl;
    }
    return 0;
}