steiner_tree.hpp¶
用子集 DP 与 Dijkstra 求非负权无向图中连接少量终端的最小代价，并可恢复原边编号；固定一个终端使状态数减半，先检查连通性，安全处理超范围代价。
Complexity: Time: \(O(t \log (t + 1) + n + m + 3^{r} n + 2^{r} (n + m) \log (n + m + 2))\), \(r = \max (k - 1 , 0)\) for \(t\) input and \(k\) distinct terminals. Space: \(O(t + 2^{r} n + n + m)\), including witness parents.
AC 记录：minimum_steiner_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(t log(t+1)+n+m+3^r n+2^r(n+m) log(n+m+2)), r=max(k-1,0)
/// for t input and k distinct terminals. Space: O(t+2^r n+n+m), including witness parents.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct steiner_tree_edge {
int a;
int b;
Weight w;
};
template <class Weight> struct steiner_tree_result {
Weight w;
std::vector<int> eid;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
/// Require valid vertices, finite nonnegative weights, and edge IDs fitting int.
/// Duplicate terminals, loops and parallel edges are allowed. No/one terminal
/// costs zero. max(Weight) is the unreachable/unrepresentable-cost sentinel;
/// finite answers must be strictly smaller. Inputs are unchanged; tied optimal
/// witnesses may differ. Selected IDs are unique and returned in increasing order.
/// At most numeric_limits<unsigned>::digits distinct terminals are supported;
/// the exponential table must fit memory. Floating arithmetic is approximate:
/// witness cost sums selected edges in ID order, which can round differently
/// from the cost-only DP.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &es,
std::vector<int> ter) {
assert(n >= 0 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
for (auto [a, b, w] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(!(w < Weight{}) && w <= std::numeric_limits<Weight>::max());
}
for (int t : ter) assert(0 <= t && t < n);
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
if (ter.size() <= 1) return {Weight{}, {}};
struct adjacent_edge {
int nxt;
Weight w;
int id;
};
std::vector<std::vector<adjacent_edge>> g(n);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
int rt = ter.back();
ter.pop_back();
const int k = int(ter.size());
assert(k < std::numeric_limits<unsigned>::digits);
const unsigned lim = 1u << k;
const Weight inf = std::numeric_limits<Weight>::max();
// Reject disconnected terminal sets before allocating the exponential table.
std::vector<unsigned char> reachable(n);
std::vector<int> queue{rt};
reachable[rt] = true;
for (std::size_t i = 0; i < queue.size(); ++i)
for (const auto &e : g[queue[i]]) if (!reachable[e.nxt]) {
reachable[e.nxt] = true;
queue.push_back(e.nxt);
}
for (int t : ter) if (!reachable[t]) return {inf, {}};
struct parent_record {
unsigned sub = 0;
int pv = -1;
int ei1 = -1;
};
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
std::vector<std::vector<parent_record>> fa(lim,
std::vector<parent_record>(n));
for (int id = 0; id < k; id++) {
dis[1u << id][ter[id]] = Weight{};
}
for (unsigned msk = 1; msk < lim; msk++) {
for (unsigned sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
unsigned rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf ||
dis[sub][u] > inf - dis[rhs][u]) {
continue;
}
Weight can = dis[sub][u] + dis[rhs][u];
if (can < dis[msk][u]) {
dis[msk][u] = can;
fa[msk][u] = {sub, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::vector<state> seeds;
seeds.reserve(n);
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) seeds.emplace_back(dis[msk][u], u);
}
std::priority_queue<state, std::vector<state>, std::greater<>>
q(std::greater<>{}, std::move(seeds));
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
if (msk == lim - 1 && u == rt) break;
for (auto e : g[u]) {
if (cur <= inf - e.w && cur + e.w < dis[msk][e.nxt]) {
dis[msk][e.nxt] = cur + e.w;
fa[msk][e.nxt] = {0, u, e.id};
q.emplace(dis[msk][e.nxt], e.nxt);
}
}
}
}
if (dis.back()[rt] == inf) {
return {inf, {}};
}
std::vector<bool> vis(es.size());
auto get = [&](auto &&self, unsigned msk, int u) -> void {
parent_record rec = fa[msk][u];
if (rec.ei1 != -1) {
self(self, msk, rec.pv);
vis[rec.ei1] = true;
} else if (rec.sub != 0) {
self(self, rec.sub, u);
self(self, msk ^ rec.sub, u);
}
};
get(get, lim - 1, rt);
std::vector<int> sel;
Weight sw{};
for (int id = 0; id < int(es.size()); id++) {
if (vis[id]) {
sel.push_back(id);
sw += es[id].w;
}
}
if constexpr (std::numeric_limits<Weight>::is_integer)
assert(sw == dis.back()[rt]);
return {sw, std::move(sel)};
}
/// @brief Minimum weight of a connected subgraph containing all ter in
/// an undirected nonnegative-weight graph. Each edge must appear in both
/// adjacency lists. The same terminal and sentinel contracts apply as above.
template <class Weight>
Weight steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &g,
std::vector<int> ter) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = int(g.size());
for (int t : ter) {
assert(0 <= t && t < n);
}
for (int u = 0; u < n; u++) {
for (auto [nxt, w] : g[u]) {
assert(0 <= nxt && nxt < n);
assert(!(w < Weight{}) && w <= std::numeric_limits<Weight>::max());
}
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
if (ter.size() <= 1) return Weight{};
int rt = ter.back();
ter.pop_back();
const int k = int(ter.size());
assert(k < std::numeric_limits<unsigned>::digits);
const unsigned lim = 1u << k;
const Weight inf = std::numeric_limits<Weight>::max();
std::vector<unsigned char> reachable(n);
std::vector<int> queue{rt};
reachable[rt] = true;
for (std::size_t i = 0; i < queue.size(); ++i)
for (const auto &[v, w] : g[queue[i]]) if (!reachable[v]) {
reachable[v] = true;
queue.push_back(v);
}
for (int t : ter) if (!reachable[t]) return inf;
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
for (int id = 0; id < k; id++) {
dis[1u << id][ter[id]] = Weight{};
}
for (unsigned msk = 1; msk < lim; msk++) {
for (unsigned sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
unsigned rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf ||
dis[sub][u] > inf - dis[rhs][u]) {
continue;
}
dis[msk][u] = std::min(dis[msk][u], dis[sub][u] + dis[rhs][u]);
}
}
using state = std::pair<Weight, int>;
std::vector<state> seeds;
seeds.reserve(n);
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) seeds.emplace_back(dis[msk][u], u);
}
std::priority_queue<state, std::vector<state>, std::greater<>>
q(std::greater<>{}, std::move(seeds));
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
if (msk == lim - 1 && u == rt) break;
for (auto [nxt, w] : g[u]) {
if (cur <= inf - w && cur + w < dis[msk][nxt]) {
dis[msk][nxt] = cur + w;
q.emplace(dis[msk][nxt], nxt);
}
}
}
}
return dis.back()[rt];
}
} // namespace noya
// NOYA_STEINER_TREE_HPP
#ifndef NOYA_STEINER_TREE_HPP
#define NOYA_STEINER_TREE_HPP 1
/// @complexity Time: O(t log(t+1)+n+m+3^r n+2^r(n+m) log(n+m+2)), r=max(k-1,0)
/// for t input and k distinct terminals. Space: O(t+2^r n+n+m), including witness parents.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct steiner_tree_edge {
int a;
int b;
Weight w;
};
template <class Weight> struct steiner_tree_result {
Weight w;
std::vector<int> eid;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
/// Require valid vertices, finite nonnegative weights, and edge IDs fitting int.
/// Duplicate terminals, loops and parallel edges are allowed. No/one terminal
/// costs zero. max(Weight) is the unreachable/unrepresentable-cost sentinel;
/// finite answers must be strictly smaller. Inputs are unchanged; tied optimal
/// witnesses may differ. Selected IDs are unique and returned in increasing order.
/// At most numeric_limits<unsigned>::digits distinct terminals are supported;
/// the exponential table must fit memory. Floating arithmetic is approximate:
/// witness cost sums selected edges in ID order, which can round differently
/// from the cost-only DP.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &es,
std::vector<int> ter) {
assert(n >= 0 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
for (auto [a, b, w] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(!(w < Weight{}) && w <= std::numeric_limits<Weight>::max());
}
for (int t : ter) assert(0 <= t && t < n);
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
if (ter.size() <= 1) return {Weight{}, {}};
struct adjacent_edge {
int nxt;
Weight w;
int id;
};
std::vector<std::vector<adjacent_edge>> g(n);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
int rt = ter.back();
ter.pop_back();
const int k = int(ter.size());
assert(k < std::numeric_limits<unsigned>::digits);
const unsigned lim = 1u << k;
const Weight inf = std::numeric_limits<Weight>::max();
// Reject disconnected terminal sets before allocating the exponential table.
std::vector<unsigned char> reachable(n);
std::vector<int> queue{rt};
reachable[rt] = true;
for (std::size_t i = 0; i < queue.size(); ++i)
for (const auto &e : g[queue[i]]) if (!reachable[e.nxt]) {
reachable[e.nxt] = true;
queue.push_back(e.nxt);
}
for (int t : ter) if (!reachable[t]) return {inf, {}};
struct parent_record {
unsigned sub = 0;
int pv = -1;
int ei1 = -1;
};
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
std::vector<std::vector<parent_record>> fa(lim,
std::vector<parent_record>(n));
for (int id = 0; id < k; id++) {
dis[1u << id][ter[id]] = Weight{};
}
for (unsigned msk = 1; msk < lim; msk++) {
for (unsigned sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
unsigned rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf ||
dis[sub][u] > inf - dis[rhs][u]) {
continue;
}
Weight can = dis[sub][u] + dis[rhs][u];
if (can < dis[msk][u]) {
dis[msk][u] = can;
fa[msk][u] = {sub, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::vector<state> seeds;
seeds.reserve(n);
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) seeds.emplace_back(dis[msk][u], u);
}
std::priority_queue<state, std::vector<state>, std::greater<>>
q(std::greater<>{}, std::move(seeds));
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
if (msk == lim - 1 && u == rt) break;
for (auto e : g[u]) {
if (cur <= inf - e.w && cur + e.w < dis[msk][e.nxt]) {
dis[msk][e.nxt] = cur + e.w;
fa[msk][e.nxt] = {0, u, e.id};
q.emplace(dis[msk][e.nxt], e.nxt);
}
}
}
}
if (dis.back()[rt] == inf) {
return {inf, {}};
}
std::vector<bool> vis(es.size());
auto get = [&](auto &&self, unsigned msk, int u) -> void {
parent_record rec = fa[msk][u];
if (rec.ei1 != -1) {
self(self, msk, rec.pv);
vis[rec.ei1] = true;
} else if (rec.sub != 0) {
self(self, rec.sub, u);
self(self, msk ^ rec.sub, u);
}
};
get(get, lim - 1, rt);
std::vector<int> sel;
Weight sw{};
for (int id = 0; id < int(es.size()); id++) {
if (vis[id]) {
sel.push_back(id);
sw += es[id].w;
}
}
if constexpr (std::numeric_limits<Weight>::is_integer)
assert(sw == dis.back()[rt]);
return {sw, std::move(sel)};
}
/// @brief Minimum weight of a connected subgraph containing all ter in
/// an undirected nonnegative-weight graph. Each edge must appear in both
/// adjacency lists. The same terminal and sentinel contracts apply as above.
template <class Weight>
Weight steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &g,
std::vector<int> ter) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = int(g.size());
for (int t : ter) {
assert(0 <= t && t < n);
}
for (int u = 0; u < n; u++) {
for (auto [nxt, w] : g[u]) {
assert(0 <= nxt && nxt < n);
assert(!(w < Weight{}) && w <= std::numeric_limits<Weight>::max());
}
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
if (ter.size() <= 1) return Weight{};
int rt = ter.back();
ter.pop_back();
const int k = int(ter.size());
assert(k < std::numeric_limits<unsigned>::digits);
const unsigned lim = 1u << k;
const Weight inf = std::numeric_limits<Weight>::max();
std::vector<unsigned char> reachable(n);
std::vector<int> queue{rt};
reachable[rt] = true;
for (std::size_t i = 0; i < queue.size(); ++i)
for (const auto &[v, w] : g[queue[i]]) if (!reachable[v]) {
reachable[v] = true;
queue.push_back(v);
}
for (int t : ter) if (!reachable[t]) return inf;
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
for (int id = 0; id < k; id++) {
dis[1u << id][ter[id]] = Weight{};
}
for (unsigned msk = 1; msk < lim; msk++) {
for (unsigned sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
unsigned rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf ||
dis[sub][u] > inf - dis[rhs][u]) {
continue;
}
dis[msk][u] = std::min(dis[msk][u], dis[sub][u] + dis[rhs][u]);
}
}
using state = std::pair<Weight, int>;
std::vector<state> seeds;
seeds.reserve(n);
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) seeds.emplace_back(dis[msk][u], u);
}
std::priority_queue<state, std::vector<state>, std::greater<>>
q(std::greater<>{}, std::move(seeds));
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
if (msk == lim - 1 && u == rt) break;
for (auto [nxt, w] : g[u]) {
if (cur <= inf - w && cur + w < dis[msk][nxt]) {
dis[msk][nxt] = cur + w;
q.emplace(dis[msk][nxt], nxt);
}
}
}
}
return dis.back()[rt];
}
} // namespace noya
#endif // NOYA_STEINER_TREE_HPP
/// @complexity Time: O(t log(t+1)+n+m+3^r n+2^r(n+m) log(n+m+2)), r=max(k-1,0)
/// for t input and k distinct terminals. Space: O(t+2^r n+n+m), including witness parents.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct steiner_tree_edge {
int a;
int b;
Weight w;
};
template <class Weight> struct steiner_tree_result {
Weight w;
std::vector<int> eid;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
/// Require valid vertices, finite nonnegative weights, and edge IDs fitting int.
/// Duplicate terminals, loops and parallel edges are allowed. No/one terminal
/// costs zero. max(Weight) is the unreachable/unrepresentable-cost sentinel;
/// finite answers must be strictly smaller. Inputs are unchanged; tied optimal
/// witnesses may differ. Selected IDs are unique and returned in increasing order.
/// At most numeric_limits<unsigned>::digits distinct terminals are supported;
/// the exponential table must fit memory. Floating arithmetic is approximate:
/// witness cost sums selected edges in ID order, which can round differently
/// from the cost-only DP.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &es,
std::vector<int> ter) {
assert(n >= 0 && es.size() <= std::size_t(std::numeric_limits<int>::max()));
for (auto [a, b, w] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(!(w < Weight{}) && w <= std::numeric_limits<Weight>::max());
}
for (int t : ter) assert(0 <= t && t < n);
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
if (ter.size() <= 1) return {Weight{}, {}};
struct adjacent_edge {
int nxt;
Weight w;
int id;
};
std::vector<std::vector<adjacent_edge>> g(n);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
int rt = ter.back();
ter.pop_back();
const int k = int(ter.size());
assert(k < std::numeric_limits<unsigned>::digits);
const unsigned lim = 1u << k;
const Weight inf = std::numeric_limits<Weight>::max();
// Reject disconnected terminal sets before allocating the exponential table.
std::vector<unsigned char> reachable(n);
std::vector<int> queue{rt};
reachable[rt] = true;
for (std::size_t i = 0; i < queue.size(); ++i)
for (const auto &e : g[queue[i]]) if (!reachable[e.nxt]) {
reachable[e.nxt] = true;
queue.push_back(e.nxt);
}
for (int t : ter) if (!reachable[t]) return {inf, {}};
struct parent_record {
unsigned sub = 0;
int pv = -1;
int ei1 = -1;
};
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
std::vector<std::vector<parent_record>> fa(lim,
std::vector<parent_record>(n));
for (int id = 0; id < k; id++) {
dis[1u << id][ter[id]] = Weight{};
}
for (unsigned msk = 1; msk < lim; msk++) {
for (unsigned sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
unsigned rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf ||
dis[sub][u] > inf - dis[rhs][u]) {
continue;
}
Weight can = dis[sub][u] + dis[rhs][u];
if (can < dis[msk][u]) {
dis[msk][u] = can;
fa[msk][u] = {sub, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::vector<state> seeds;
seeds.reserve(n);
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) seeds.emplace_back(dis[msk][u], u);
}
std::priority_queue<state, std::vector<state>, std::greater<>>
q(std::greater<>{}, std::move(seeds));
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
if (msk == lim - 1 && u == rt) break;
for (auto e : g[u]) {
if (cur <= inf - e.w && cur + e.w < dis[msk][e.nxt]) {
dis[msk][e.nxt] = cur + e.w;
fa[msk][e.nxt] = {0, u, e.id};
q.emplace(dis[msk][e.nxt], e.nxt);
}
}
}
}
if (dis.back()[rt] == inf) {
return {inf, {}};
}
std::vector<bool> vis(es.size());
auto get = [&](auto &&self, unsigned msk, int u) -> void {
parent_record rec = fa[msk][u];
if (rec.ei1 != -1) {
self(self, msk, rec.pv);
vis[rec.ei1] = true;
} else if (rec.sub != 0) {
self(self, rec.sub, u);
self(self, msk ^ rec.sub, u);
}
};
get(get, lim - 1, rt);
std::vector<int> sel;
Weight sw{};
for (int id = 0; id < int(es.size()); id++) {
if (vis[id]) {
sel.push_back(id);
sw += es[id].w;
}
}
if constexpr (std::numeric_limits<Weight>::is_integer)
assert(sw == dis.back()[rt]);
return {sw, std::move(sel)};
}
/// @brief Minimum weight of a connected subgraph containing all ter in
/// an undirected nonnegative-weight graph. Each edge must appear in both
/// adjacency lists. The same terminal and sentinel contracts apply as above.
template <class Weight>
Weight steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &g,
std::vector<int> ter) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = int(g.size());
for (int t : ter) {
assert(0 <= t && t < n);
}
for (int u = 0; u < n; u++) {
for (auto [nxt, w] : g[u]) {
assert(0 <= nxt && nxt < n);
assert(!(w < Weight{}) && w <= std::numeric_limits<Weight>::max());
}
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
if (ter.size() <= 1) return Weight{};
int rt = ter.back();
ter.pop_back();
const int k = int(ter.size());
assert(k < std::numeric_limits<unsigned>::digits);
const unsigned lim = 1u << k;
const Weight inf = std::numeric_limits<Weight>::max();
std::vector<unsigned char> reachable(n);
std::vector<int> queue{rt};
reachable[rt] = true;
for (std::size_t i = 0; i < queue.size(); ++i)
for (const auto &[v, w] : g[queue[i]]) if (!reachable[v]) {
reachable[v] = true;
queue.push_back(v);
}
for (int t : ter) if (!reachable[t]) return inf;
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
for (int id = 0; id < k; id++) {
dis[1u << id][ter[id]] = Weight{};
}
for (unsigned msk = 1; msk < lim; msk++) {
for (unsigned sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
unsigned rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf ||
dis[sub][u] > inf - dis[rhs][u]) {
continue;
}
dis[msk][u] = std::min(dis[msk][u], dis[sub][u] + dis[rhs][u]);
}
}
using state = std::pair<Weight, int>;
std::vector<state> seeds;
seeds.reserve(n);
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) seeds.emplace_back(dis[msk][u], u);
}
std::priority_queue<state, std::vector<state>, std::greater<>>
q(std::greater<>{}, std::move(seeds));
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
if (msk == lim - 1 && u == rt) break;
for (auto [nxt, w] : g[u]) {
if (cur <= inf - w && cur + w < dis[msk][nxt]) {
dis[msk][nxt] = cur + w;
q.emplace(dis[msk][nxt], nxt);
}
}
}
}
return dis.back()[rt];
}
} // namespace noya
// NOYA_STEINER_TREE_HPP