ワーシャルフロイド 参照用 (クラスVerは最下)

// 隣接行列
ll d[100][100];

int main(){
    // input
    ll N, M;
    cin >> N >> M;

    // 隣接行列の初期値。infにする
    rep(i, N){
      rep(j, N){
        if(i!=j) d[i][j] = inf;
      }
    }

    // 距離データ入力
    rep(i, M){
      ll a, b, c;
      cin >> a >> b >> c;
      a--; b--;
      d[a][b] = c;
      d[b][a] = c;
    }

    // ワーシャルフロイド
    rep(i, N){ // 経由点
      rep(j, N){ // 始点
         rep(k, N){ // 終点
          d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
        }
      }
    }

    // 使う
    // 略
}

目的

  • コピー用
  • 行列初期化を忘れるというミスをした。それを今後は防ぐため

verified

クラス化

  • クラス化しておくと使いやすい
// 必要メモリ O(N^2)
// 計算量 O(N^3)
struct WarshallFloyd{
  VV d;
  ll N;
  bool pre_calculated = false;
  WarshallFloyd(ll n){
    if(n>=2000){
      cerr << "[warning]maybe data size is too big";
    }
    N = n;
    d.resize(N, VI(N, inf));
    rep(i, N) d[i][i] = 0;
  }
  // 単方向
  void register_edge(ll a, ll b, ll c){
    d[a][b] = c;
  }
  // 双方向
  void register_edge2(ll a, ll b, ll c){
    register_edge(a,b,c);
    register_edge(b,a,c);
  }
  void calc(){
    rep(i, N){ // 経由点
      rep(j, N){ // 始点
         rep(k, N){ // 終点
          d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
        }
      }
    }
    pre_calculated = true;
  }
  ll distance(ll a, ll b){
    // 計算忘れ対応
    if(!pre_calculated){
      debug("auto calc");
      calc();
    }
    return d[a][b];
  }
};

verified