This problem is an extension of a famous problem called minimum Steiner tree problem. We referred to an editorial slide by Yoichi Iwata.

We call a city, road, and cost simply a vertex, edge, and weight.

First of all, in an optimal solution the graph defined by the set of edges to be extended as well as their adjacent vertices obviously form a tree.

For a non-empty subset of the vertex set \(\{1,2,\dots,K-1\}\) and a vertex \(v\), we define \(f(S,v)\) as the minimum total weights of the edges of a tree containing vertex \(v\) and all vertices in \(S\). What we finally want is \(f(\{1,2,\dots,K-1\}, v)\) for each \(K\leq v\leq N\).

The conclusion is that \(f(S,v)\) can be evaluated with Dynamic Programming (DP). With initial values \(f(\{i\}, i)=0\ (1 \leq i \leq K-1)\), there are two kinds of transitions:

• \(f(S,v) \leftarrow \min(f(S,v),f(S,u) + w)\) (An edge of weight \(w\) connecting vertices \(u\) and \(v\) exists)
• \(f(S,v) \leftarrow \min(f(S,v),f(T,v)+f(S\setminus T,v))\ (T\subsetneq S, T\neq \emptyset)\)

The transitions can be interpreted (somewhat informally) as follows:

• Former: if \(v\) is not in \(S\) and is a tree of the tree, remove \(v\) and the only adjacent edge from the tree.
• Latter: otherwise, partition \(S\) into two non-empty sets \(T\) and \(S\setminus T\) (which is always possible in an optimal solution):
  • the intersection of the following is empty: the set of edges connecting \(v\) and each vertex in \(T\), and the set of edges connecting \(v\) and each vertex in \(S\setminus T\), in \(T\).

All that left is how to process these transitions. The latter can be handled by filling the DP table in ascending order of the size of \(S\). The problem is the circular dependency in the former transitions, which can be handled by determining \(f(S,v)\ (1\leq v\leq N)\) in ascending order of its value in the manner of Dijkstra’s algorithm.

The overall complexity is \(O(3^KN+2^KM\log M)\).

Sample code (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';
    }
}