本問題は最小シュタイナー木問題と呼ばれる有名問題の派生問題です。本解説は 岩田陽一さんによる解説スライドを参考に執筆されています。

以下、都市、道路、コストのことをそれぞれ単に頂点、辺、重みと呼びます。

まず、最適解において拡張される辺の集合およびそれに隣接する頂点の集合からなるグラフは明らかに木をなします。

頂点集合 \(\{1,2,\dots,K-1\}\) の任意の非空な部分集合 \(S\) および任意の頂点 \(v\) に対して、\(f(S,v)\) を「\(S\) に含まれる各頂点と頂点 \(v\) を共に含むような木の辺の重みの総和の最小値」と定義します。最終的に求めたいのは各 \(K\leq v\leq N\) に対する \(f(\{1,2,\dots,K-1\}, v)\) の値です。

結論としては、各 \(f(S,v)\) の値は動的計画法によって求めることができます。初期値は \(f(\{i\}, i)=0\ (1 \leq i \leq K-1)\) であり、遷移は以下の二通りです :

• \(f(S,v) \leftarrow \min(f(S,v),f(S,u) + w)\) （頂点 \(u,v\) を結ぶ重み \(w\) の辺が存在）
• \(f(S,v) \leftarrow \min(f(S,v),f(T,v)+f(S\setminus T,v))\ (T\subsetneq S, T\neq \emptyset)\)

各遷移は以下のように解釈（厳密な証明ではない）できます :

• \(1\) つめの遷移 : \(v\) が \(S\) に含まれず、\(v\) が木の葉であるようなとき、木から \(v\) とそれに接続する唯一の辺を削除する
• \(2\) つめの遷移 : そうでないとき、\(S\) を以下の条件を満たす \(2\) つのひくうな集合 \(T,S\setminus T\) に分割する（最適解においては必ず可能である）
  • 木において 「\(T\) に含まれる各頂点と \(v\) を結ぶパスに含まれる辺の集合」と「\(S\setminus T\) に含まれる各頂点と \(v\) を結ぶパスに含まれる辺の集合」の共通集合が空である

残る問題はこれらの遷移をどのように処理するかです。\(2\) つめの遷移は DP テーブルの値を \(S\) の要素数の昇順などで埋めていけば問題ありません。問題は同じ \(S\) 内で \(1\) つめの遷移の依存関係が循環してしまっていることですが、これについては Dijkstra 法のように各 \(f(S,v)\ (1\leq v\leq N)\) の値を値の小さい順に確定させていくことで対処できます。

全体の計算量は \(O(3^KN+2^KM\log M)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

bool chmin(ll &a, ll b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    --k;
    vector<vector<pair<int, int>>> G(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }
    vector dp(1 << k, vector<ll>(n, 1e18));
    for (int i = 0; i < k; i++) dp[1 << i][i] = 0;
    for (int bit = 1; bit < (1 << k); bit++) {
        for (int sub = bit; sub > 0; sub = (sub - 1) & bit) {
            for (int i = 0; i < n; i++) {
                chmin(dp[bit][i], dp[sub][i] + dp[bit - sub][i]);
            }
        }
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        for (int i = 0; i < n; i++) pq.emplace(dp[bit][i], i);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dp[bit][u]) continue;
            for (auto [v, l]: G[u]) {
                if (chmin(dp[bit][v], d + l)) {
                    pq.emplace(d + l, v);
                }
            }
        }
    }
    for (int i = k; i < n; i++) {
        cout << dp.back()[i] << '\n';
    }
}