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

問題ページ
C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder

考えたこと

• Sを求めるには全点対の最短距離が必要
• ワーシャルフロイドをしたい
• 辺を追加するクエリの度にワーシャルフロイドしてO(N^3)かけていたらO(N^3K)でまず通らない
• グラフ中で高々1本しか辺が増えないのに全頂点に対して最短距離を計算するのは無駄そう
• 頂点x,yに辺を追加するとき、頂点集合G={i|i∉x,y}に対する最短距離はすでに求まっている
• したがってワーシャルフロイドで中間として通る点として考えるのはx,yのいずれかのみでよい
• 辺の追加1回ごとにO(N^2)しかかからない
• 合計でO(N^2K)でこれなら通る

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

const int INF = (1LL<<30);

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }

int d[405][405];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  REP(i, n) REP(j, n) d[i][j] = i==j?0:INF;
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    d[a][b] = d[b][a] = c;
  }

  REP(k, n) REP(i, n) REP(j, n) chmin(d[i][j], d[i][k]+d[k][j]);
  int all = 0;
  REP(i, n) REP(j, n) if(d[i][j]!=INF) all += d[i][j];

  int K;
  cin >> K;
  REP(_, K) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    if(d[a][b] < c) {
      cout << all/2 << endl;
      continue;
    }
    d[a][b] = d[b][a] = c;
    // 頂点aを中間地点とするとき
    REP(i, n) REP(j, n) chmin(d[i][j], d[i][a]+d[a][j]);
    // 頂点bを中間地点とするとき
    REP(i, n) REP(j, n) chmin(d[i][j], d[i][b]+d[b][j]);
    all = 0;
    REP(i, n) REP(j, n) if(d[i][j]!=INF) all += d[i][j];
    cout << all/2 << endl;
  }

  return 0;
}