// #include // // #include "graph/read_graph.hpp" // #include "graph/minimum_steiner_tree.hpp" // // int main() { // int N, M, T; // std::cin >> N >> M >> T; // // if (T <= 15) { // auto g = read_graph(N, M, true); // std::vector terminals(T); // for (int i = 0; i < T; i++) { // std::cin >> terminals[i]; // terminals[i]--; // } // auto dp = minimum_steiner_tree(g, terminals, 1'000'000'000); // std::cout << dp.back()[terminals[0]] << '\n'; // } else { // std::vector> es(M); // for (int i = 0; i < M; i++) { // int a, b, c; // std::cin >> a >> b >> c; // a--, b--; // es[i] = Edge(a, b, c, i); // } // std::vector terminals(T); // for (int i = 0; i < T; i++) { // std::cin >> terminals[i]; // terminals[i]--; // } // std::cout << minimum_steiner_tree_mst(es, N, terminals, 1'000'000'000) << '\n'; // } // return 0; // } #include #include template struct Edge { int from, to; T cost; int id; Edge() = default; Edge(int from, int to, T cost = 1, int id = -1) : from(from), to(to), cost(cost), id(id) {} friend std::ostream& operator<<(std::ostream& os, const Edge& e) { // output format: "{ id : from -> to, cost }" return os << "{ " << e.id << " : " << e.from << " -> " << e.to << ", " << e.cost << " }"; } }; template using Edges = std::vector>; template using Graph = std::vector>>; template Graph read_graph(const int n, const int m, const bool weight = false, const bool directed = false, const int offset = 1) { Graph g(n); for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; a -= offset, b -= offset; if (weight) { T c; std::cin >> c; if (!directed) g[b].push_back(Edge(b, a, c, i)); g[a].push_back(Edge(a, b, c, i)); } else { // c = 1 if (!directed) g[b].push_back(Edge(b, a, T(1), i)); g[a].push_back(Edge(a, b, T(1), i)); } } return g; } template Graph read_parent(const int n, const bool weight = false, const bool directed = false, const int offset = 1) { Graph g(n); for (int i = 1; i < n; i++) { int p; std::cin >> p; p -= offset; if (weight) { T c; std::cin >> c; if (!directed) g[i].push_back(Edge(i, p, c, i - 1)); g[p].push_back(Edge(p, i, c, i - 1)); } else { // c = 1 if (!directed) g[i].push_back(Edge(i, p, T(1), i - 1)); g[p].push_back(Edge(p, i, T(1), i - 1)); } } return g; } #include #include #include struct UnionFind { int n; std::vector parents; UnionFind() {} UnionFind(int n) : n(n), parents(n, -1) {} int leader(int x) { return parents[x] < 0 ? x : parents[x] = leader(parents[x]); } bool merge(int x, int y) { x = leader(x), y = leader(y); if (x == y) return false; if (parents[x] > parents[y]) std::swap(x, y); parents[x] += parents[y]; parents[y] = x; return true; } bool same(int x, int y) { return leader(x) == leader(y); } int size(int x) { return -parents[leader(x)]; } std::vector> groups() { std::vector leader_buf(n), group_size(n); for (int i = 0; i < n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(n); for (int i = 0; i < n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); } result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } void init(int n) { parents.assign(n, -1); } // reset }; // minimum steiner tree // O(3 ^ k n + 2 ^ k m \log m) (n = |V|, m = |E|, k = |terminals|) // https://www.slideshare.net/wata_orz/ss-12131479#50 // https://kopricky.github.io/code/Academic/steiner_tree.html // https://atcoder.jp/contests/abc364/editorial/10547 template std::vector> minimum_steiner_tree(Graph& g, std::vector& terminals, const T inf) { const int n = (int)(g.size()); const int k = (int)(terminals.size()); const int k2 = 1 << k; // dp[bit][v] = ターミナルの部分集合が bit (0 ~ k - 1 に圧縮), 加えて頂点 v も含まれる最小シュタイナー木 std::vector dp(k2, std::vector(n, inf)); for (int i = 0; i < k; i++) dp[1 << i][terminals[i]] = T(0); for (int bit = 0; bit < (1 << k); bit++) { // dp[bit][v] = min(dp[bit][v], dp[sub][v] + dp[bit ^ sub][v]) // 通常の実装 // for (int sub = bit; sub > 0; sub = (sub - 1) & bit) { // 定数倍高速化 // bit の中で 1 要素だけ sub と bit ^ sub のどちらに属するか決める int bit2 = bit ^ (bit & -bit); for (int sub = bit2; sub > 0; sub = (sub - 1) & bit2) { for (int v = 0; v < n; v++) { dp[bit][v] = std::min(dp[bit][v], dp[sub][v] + dp[bit ^ sub][v]); } } // dp[bit][v] = min(dp[bit][v], dp[bit][u] + cost(u, v)) using tp = std::pair; std::priority_queue, std::greater> que; for (int u = 0; u < n; u++) que.emplace(dp[bit][u], u); while (!que.empty()) { auto [d, u] = que.top(); que.pop(); if (dp[bit][u] != d) continue; for (auto&& e : g[u]) { if (dp[bit][e.to] > d + e.cost) { dp[bit][e.to] = d + e.cost; que.emplace(dp[bit][e.to], e.to); } } } } // dp[k2 - 1][i] = ターミナルと頂点 i を含む最小シュタイナー木 // dp[k2 - 1][terminals[0]] が基本的な答えになる return dp; } // O(2 ^ {n - k} (n + m)) (n = |V|, m = |E|, k = |terminals|) // https://yukicoder.me/problems/no/114/editorial // n - k <= 20 template T minimum_steiner_tree_mst(Edges& edges, const int n, std::vector& terminals, const T inf) { const int k = (int)(terminals.size()); // ターミナルに含まれない点集合 (others) を取得 std::vector used(n, 0); for (int i = 0; i < k; i++) used[terminals[i]] = 1; std::vector others; for (int i = 0; i < n; i++) { if (used[i] == 0) others.push_back(i); } std::sort(edges.begin(), edges.end(), [&](Edge& a, Edge& b) -> bool { return a.cost < b.cost; }); // ターミナル + others の組合せを全列挙 -> Minimum Spanning Tree を求める T ans = inf; for (int bit = 0; bit < (1 << (n - k)); bit++) { // 使う頂点集合 (used) を計算 for (int i = 0; i < n - k; i++) used[others[i]] = bit >> i & 1; // Minimum Spanning Tree を計算 UnionFind uf(n); T cur = 0; int connected = 0; for (auto&& e : edges) { // subv に対する g の誘導部分グラフに含まれる辺のみ試す if (!(used[e.from] and used[e.to])) continue; if (!uf.same(e.from, e.to)) { uf.merge(e.from, e.to); cur += e.cost; connected++; } } // 全域木が作れたか判定 if (connected + 1 == k + __builtin_popcount(bit)) ans = std::min(ans, cur); // used をもとに戻す for (int i = 0; i < n - k; i++) used[others[i]] = 0; } return ans; } int main() { int N, M, T; std::cin >> N >> M >> T; if (T <= 15) { auto g = read_graph(N, M, true); std::vector terminals(T); for (int i = 0; i < T; i++) { std::cin >> terminals[i]; terminals[i]--; } auto dp = minimum_steiner_tree(g, terminals, 1'000'000'000); std::cout << dp.back()[terminals[0]] << '\n'; } else { std::vector> es(M); for (int i = 0; i < M; i++) { int a, b, c; std::cin >> a >> b >> c; a--, b--; es[i] = Edge(a, b, c, i); } std::vector terminals(T); for (int i = 0; i < T; i++) { std::cin >> terminals[i]; terminals[i]--; } std::cout << minimum_steiner_tree_mst(es, N, terminals, 1'000'000'000) << '\n'; } return 0; }