E

简单 dp，两维限制转成一维。

F

区间建边的 MST，可以考虑区间取 min，是等价的。

G

斯坦纳树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<pair<int, int>>> e(n);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    e[u].emplace_back(v, w);
    e[v].emplace_back(u, w);
  }
  k--;
  vector<int> p(k);
  for (int i = 0; i < k; i++) {
    p[i] = i;
  }
  vector<vector<int>> dp(n, vector<int>(1 << k, INF));
  for (int i = 0; i < k; i++) {
    dp[p[i]][1 << i] = 0;
  }
  for (int s = 0; s < 1 << k; s++) {
    for (int i = 0; i < n; i++) {
      for (int t = s; t; --t &= s) {
        dp[i][s] = min(dp[i][s], dp[i][t] + dp[i][s ^ t]);
      }
    }
    vector<bool> vis(n);
    vector<int> dis(n);
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        q;
    for (int i = 0; i < n; i++) {
      dis[i] = dp[i][s];
      q.emplace(dp[i][s], i);
    }
    while (!q.empty()) {
      auto t = q.top();
      q.pop();
      int u = t.second;
      if (vis[u]) {
        continue;
      }
      vis[u] = 1;
      for (auto x : e[u]) {
        int v = x.first;
        int w = x.second;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          q.emplace(dis[v], v);
        }
      }
    }
    for (int i = 0; i < n; i++) {
      dp[i][s] = dis[i];
    }
  }

  for (int i = k; i < n; i++) {
    cout << dp[i][(1 << k) - 1] << "\n";
  }
  return 0;
}