【C++】すべてのトリプレットにおける最短コストパスの合計を求めるプログラム

n個の都市と、それらをつなぐm本の道路があるとします。各道路は {始点, 終点, 重み} という形式で配列として与えられます。ここで、3つの都市 s・t・k からなるトリプレット (s, t, k) を考えます。このとき、都市 s から都市 t へ移動するために必要な最小時間を求めます。ただし、s から t へ移動する際には、番号 1 から k までの都市だけを経由することができます。もし t に到達できない場合は 0 を返します。すべてのトリプレット (s, t, k) について最小時間を計算し、その合計を出力してください。

たとえば、入力が n = 4、m = 2、edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}} の場合、出力は 63 になります。

解き方のポイント：ワーシャル・フロイド法

この問題は、全点対最短経路を段階的に求める「ワーシャル・フロイド法（Floyd–Warshall法）」を使うと効率的に解けます。中継地点として使える都市を1つずつ増やしながら距離行列を更新していくことで、「都市 1〜k のみを経由してよい」という条件付きの最短距離を自然に計算でき、その都度合計を加算していきます。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

値が無限大（INF）で初期化された2次元配列 dvec を定義する
i := 0 から i < n まで、i を1ずつ増やしながら繰り返す：
    dvec[i, i] := 0
i := 0 から i < m まで、i を1ずつ増やしながら繰り返す：
    a := edges[i] の1番目の値
    b := edges[i] の2番目の値
    c := edges[i] の3番目の値
    a と b をそれぞれ1減らす
    dvec[a, b] := c
res := 0
k := 0 から k < n まで、k を1ずつ増やしながら繰り返す：
    i := 0 から i < n まで、i を1ずつ増やしながら繰り返す：
        j := 0 から j < n まで、j を1ずつ増やしながら繰り返す：
            dvec[i, j] := min(dvec[i, j], dvec[i, k] + dvec[k, j])
            もし dvec[i, j] が無限大でなければ：
                res := res + dvec[i, j]
res を出力する

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

void solve(int n, int m, vector<tuple<int, int, int>> edges){
   vector<vector<int>> dvec(n, vector<int>(n, INF));
   for(int i = 0; i < n; i++)
      dvec[i][i] = 0;
   for(int i = 0; i < m; i++) {
      int a = get<0>(edges[i]);
      int b = get<1>(edges[i]);
      int c = get<2>(edges[i]);
      a--; b--;
      dvec[a][b] = c;
   }
   int res = 0;
   for(int k = 0; k < n; k++) {
      for(int i = 0; i < n; i++) {
         for(int j = 0; j < n; j++) {
            dvec[i][j] = min(dvec[i][j], dvec[i][k]+dvec[k][j]);
            if(dvec[i][j] != INF)
               res += dvec[i][j];
         }
      }
   }
   cout << res << endl;
}
int main() {
   int n = 4, m = 2;
   vector<tuple<int, int, int>> edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}};
   solve(n, m, edges);
   return 0;
}

入力

4, 2, {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}

出力

63

このアルゴリズムの計算量は O(n³) であり、都市数 n が比較的小さい場合に特に有効です。三重ループの中で中継都市 k を順に許可していくことで、すべてのトリプレットに対する条件付き最短距離を重複なく集計できるのが大きな特徴です。