cp-library
競技プログラミング用 C++ ライブラリ
test/steiner_tree.test.cpp
test/steiner_tree.test.cpp · GitHub で見る
依存ライブラリ
コード
#define PROBLEM "https://judge.yosupo.jp/problem/minimum_steiner_tree"
#include "../graph/steiner_tree.hpp"
#include "../components/fast_io.hpp"
int main() {
FastInput input;
FastOutput output;
int n = 0, m = 0;
input.read(n), input.read(m);
SteinerTree<> graph(n);
graph.reserve(m);
for (int i = 0; i < m; ++i) {
int u = 0, v = 0;
std::int64_t w = 0;
input.read(u), input.read(v), input.read(w);
graph.add_edge(u, v, w);
}
int k = 0;
input.read(k);
std::vector<int> terminals(k);
for (int &v : terminals) input.read(v);
auto result = graph.solve(terminals);
assert(result);
output.write(result->cost), output.write(' '), output.write(result->edges.size()), output.write('\n');
for (std::size_t i = 0; i < result->edges.size(); ++i) {
if (i) output.write(' ');
output.write(result->edges[i]);
}
output.write('\n');
}
#line 1 "test/steiner_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/minimum_steiner_tree"
#line 1 "graph/steiner_tree.hpp"
#line 1 "components/dijkstra_queue.hpp"
#line 1 "components/RadixHeap.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
template <class Key = std::uint64_t, class T = int>
class RadixHeap {
static_assert(std::is_integral_v<Key> && !std::is_same_v<Key, bool> && sizeof(Key) <= 8);
using U = std::make_unsigned_t<Key>;
using State = std::pair<Key, T>;
std::vector<State> bucket[std::numeric_limits<U>::digits + 1];
Key lower;
std::size_t count = 0;
int index(Key key) const { return std::bit_width(U(U(key) ^ U(lower))); }
void refill() {
assert(count);
if (!bucket[0].empty()) return;
int i = 1;
while (bucket[i].empty()) ++i;
lower = bucket[i][0].first;
for (const auto &s : bucket[i]) lower = std::min(lower, s.first);
for (auto &s : bucket[i]) bucket[index(s.first)].push_back(std::move(s));
bucket[i].clear();
}
public:
explicit RadixHeap(Key minimum = 0) : lower(minimum) {}
RadixHeap(const RadixHeap &) = default;
RadixHeap &operator=(const RadixHeap &) = default;
RadixHeap(RadixHeap &&other) noexcept : lower(other.lower), count(std::exchange(other.count, 0)) {
for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
}
RadixHeap &operator=(RadixHeap &&other) noexcept {
if (this != &other) {
lower = other.lower;
count = std::exchange(other.count, 0);
for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
}
return *this;
}
bool empty() const { return count == 0; }
std::size_t size() const { return count; }
Key last() const { return lower; }
void clear(Key minimum = 0) {
for (auto &b : bucket) b.clear();
lower = minimum;
count = 0;
}
void push(State s) {
assert(s.first >= lower);
bucket[index(s.first)].push_back(std::move(s));
++count;
}
const State &top() {
refill();
return bucket[0].back();
}
void pop() {
refill();
bucket[0].pop_back();
--count;
}
State pop_value() {
refill();
State s = std::move(bucket[0].back());
bucket[0].pop_back();
--count;
return s;
}
};
#line 10 "components/dijkstra_queue.hpp"
#include <functional>
#line 15 "components/dijkstra_queue.hpp"
namespace shortest_path_detail {
template<class Weight, class Distance>
bool reaches_limit(const Weight &weight, const Distance &limit) {
if constexpr (std::numeric_limits<Weight>::is_integer && std::numeric_limits<Weight>::is_bounded &&
std::numeric_limits<Distance>::is_integer && std::numeric_limits<Distance>::is_bounded) {
using Compare = std::common_type_t<Weight, Distance>;
return Compare(weight) >= Compare(limit);
} else return weight >= limit;
}
template<class T> class RadixQueue {
static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
struct State { T key; int vertex; };
State small_[32];
std::vector<std::uint64_t> buckets_[33];
std::uint32_t minimum_[33];
std::uint32_t occupied_ = 0;
std::uint64_t last_ = 0;
std::size_t count_ = 0;
int mode_ = 0;
RadixHeap<std::uint64_t> wide_;
void put(std::uint64_t state) {
std::uint32_t key = state >> 32;
int index = std::bit_width(key ^ std::uint32_t(last_));
buckets_[index].push_back(state);
if (index) {
occupied_ |= std::uint32_t(1) << (index - 1);
minimum_[index] = std::min(minimum_[index], key);
}
}
void promote() {
if (mode_ == 0) {
for (std::size_t i = 0; i < count_; ++i) wide_.push({std::uint64_t(small_[i].key), small_[i].vertex});
} else {
for (auto &bucket : buckets_) {
for (auto state : bucket) {
std::uint64_t key = last_ + std::uint32_t(std::uint32_t(state >> 32) - std::uint32_t(last_));
wide_.push({key, int(std::uint32_t(state))});
}
bucket.clear();
}
}
mode_ = 2;
}
public:
bool empty() const { return count_ == 0; }
void push(T key, int vertex) {
assert(key >= 0 && std::uint64_t(key) >= last_);
if (mode_ == 0 && count_ < 32) {
small_[count_++] = {key, vertex};
return;
}
if (mode_ == 0) {
bool narrow = std::uint64_t(key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
for (std::size_t i = 0; i < count_; ++i)
narrow &= std::uint64_t(small_[i].key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
if (narrow) {
std::fill_n(minimum_, 33, std::numeric_limits<std::uint32_t>::max());
for (std::size_t i = 0; i < count_; ++i)
put((std::uint64_t(std::uint32_t(small_[i].key)) << 32) | std::uint32_t(small_[i].vertex));
mode_ = 1;
} else promote();
}
if (mode_ == 1 && std::uint64_t(key) - last_ > std::uint64_t(std::numeric_limits<std::int32_t>::max())) promote();
if (mode_ == 2) wide_.push({std::uint64_t(key), vertex});
else put((std::uint64_t(std::uint32_t(key)) << 32) | std::uint32_t(vertex));
++count_;
}
std::pair<T, int> pop() {
assert(count_);
if (mode_ == 0) {
std::size_t best = 0;
for (std::size_t i = 1; i < count_; ++i)
if (small_[i].key < small_[best].key) best = i;
State state = small_[best];
small_[best] = small_[--count_];
last_ = std::uint64_t(state.key);
return {state.key, state.vertex};
}
if (mode_ == 2) {
auto state = wide_.pop_value();
last_ = state.first;
--count_;
return {T(state.first), state.second};
}
if (buckets_[0].empty()) {
int index = std::countr_zero(occupied_) + 1;
last_ += std::uint32_t(minimum_[index] - std::uint32_t(last_));
minimum_[index] = std::numeric_limits<std::uint32_t>::max();
occupied_ &= occupied_ - 1;
if (buckets_[index].size() == 1) {
auto state = buckets_[index].back();
buckets_[index].clear();
--count_;
return {T(last_), int(std::uint32_t(state))};
}
for (auto state : buckets_[index]) put(state);
buckets_[index].clear();
}
auto state = buckets_[0].back();
buckets_[0].pop_back();
--count_;
return {T(last_), int(std::uint32_t(state))};
}
};
template<class T> class BinaryQueue {
using State = std::pair<T, int>;
std::vector<State> heap_;
public:
bool empty() const { return heap_.empty(); }
void push(T cost, int vertex) {
heap_.emplace_back(std::move(cost), vertex);
std::push_heap(heap_.begin(), heap_.end(), std::greater<State>());
}
State pop() {
std::pop_heap(heap_.begin(), heap_.end(), std::greater<State>());
State state = std::move(heap_.back());
heap_.pop_back();
return state;
}
};
template<class T>
using DistanceQueue = std::conditional_t<std::is_integral_v<T> && sizeof(T) <= 8, RadixQueue<T>, BinaryQueue<T>>;
}
#line 1 "components/undirected_csr.hpp"
#line 7 "components/undirected_csr.hpp"
#include <memory>
#include <span>
#line 12 "components/undirected_csr.hpp"
namespace undirected_csr_detail {
template <class Arc>
void build(int n, std::span<const std::pair<int, int>> edges, std::vector<int>& start, std::unique_ptr<Arc[]>& adj) {
assert(0 <= n && n < std::numeric_limits<int>::max());
assert(edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
start.assign(std::size_t(n) + 1, 0);
for (auto [u, v] : edges) {
assert(0 <= u && u < n && 0 <= v && v < n);
++start[u + 1], ++start[v + 1];
}
for (int v = 0; v < n; ++v) start[v + 1] += start[v];
adj.reset(new Arc[2 * edges.size()]);
std::vector<int> cursor(start.begin(), start.end() - 1);
for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
auto [u, v] = edges[i];
if constexpr (std::is_same_v<Arc, int>) adj[cursor[u]++] = v, adj[cursor[v]++] = u;
else adj[cursor[u]++] = {v, i}, adj[cursor[v]++] = {u, i};
}
}
}
struct UndirectedCSR {
struct Arc { int to, id; };
int n;
std::vector<int> start;
std::unique_ptr<Arc[]> adj;
UndirectedCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
undirected_csr_detail::build(n, edges, start, adj);
}
std::span<const Arc> operator[](int v) const {
assert(0 <= v && v < n);
return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
}
};
struct UndirectedVertexCSR {
int n;
std::vector<int> start;
std::unique_ptr<int[]> adj;
UndirectedVertexCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
undirected_csr_detail::build(n, edges, start, adj);
}
std::span<const int> operator[](int v) const {
assert(0 <= v && v < n);
return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
}
};
#line 1 "data_structure/union_find.hpp"
#line 7 "data_structure/union_find.hpp"
class UnionFind {
std::vector<int> parent_;
int count_ = 0;
public:
explicit UnionFind(int n = 0) : count_(n) {
assert(n >= 0);
parent_.assign(n, -1);
}
[[nodiscard]] int size() const { return static_cast<int>(parent_.size()); }
[[nodiscard]] int count() const { return count_; }
[[nodiscard]] int leader(int v) {
assert(0 <= v && v < size());
while (parent_[v] >= 0) {
int p = parent_[v];
if (parent_[p] < 0) return p;
v = parent_[v] = parent_[p];
}
return v;
}
int merge(int a, int b) {
a = leader(a), b = leader(b);
if (a == b) return a;
if (parent_[a] > parent_[b]) std::swap(a, b);
parent_[a] += parent_[b];
parent_[b] = a;
--count_;
return a;
}
[[nodiscard]] bool same(int a, int b) { return leader(a) == leader(b); }
[[nodiscard]] int size(int v) { return -parent_[leader(v)]; }
[[nodiscard]] std::vector<std::vector<int>> groups() {
std::vector<int> index(size(), -1);
std::vector<std::vector<int>> result(count_);
int next = 0;
for (int v = 0; v < size(); ++v) if (parent_[v] < 0) {
index[v] = next;
result[next++].reserve(-parent_[v]);
}
for (int v = 0; v < size(); ++v) result[index[leader(v)]].push_back(v);
return result;
}
};
#line 13 "graph/steiner_tree.hpp"
#include <optional>
#include <stdexcept>
#line 18 "graph/steiner_tree.hpp"
template<class Cost = std::int64_t, class Sum = Cost>
class SteinerTree {
static_assert((std::numeric_limits<Cost>::is_integer || std::is_floating_point_v<Cost>) && !std::is_same_v<Cost, bool>);
static_assert((std::numeric_limits<Sum>::is_integer || std::is_floating_point_v<Sum>) && !std::is_same_v<Sum, bool>);
static_assert(std::numeric_limits<Cost>::is_integer == std::numeric_limits<Sum>::is_integer);
static_assert(std::numeric_limits<Cost>::digits <= std::numeric_limits<Sum>::digits);
int n_;
public:
struct Edge { int from, to; Cost cost; };
struct Result { Sum cost = 0; std::vector<int> edges; };
private:
std::vector<Edge> edges_;
template<bool Restore>
std::optional<Result> run(std::vector<int> terminals, Sum inf) const {
assert(inf > 0);
for ([[maybe_unused]] int v : terminals) assert(0 <= v && v < n_);
std::sort(terminals.begin(), terminals.end());
terminals.erase(std::unique(terminals.begin(), terminals.end()), terminals.end());
if (terminals.size() <= 1) return Result{};
int root = terminals.back();
terminals.pop_back();
auto graph = [&] {
std::vector<std::pair<int, int>> endpoints;
endpoints.reserve(edges_.size());
for (const auto &e : edges_) endpoints.emplace_back(e.from, e.to);
return UndirectedCSR(n_, endpoints);
}();
{
std::vector<unsigned char> seen(n_);
std::vector<int> work{root};
seen[root] = 1;
for (std::size_t i = 0; i < work.size(); ++i)
for (auto [u, id] : graph[work[i]]) if (!seen[u] && Sum(edges_[id].cost) < inf) {
seen[u] = 1, work.push_back(u);
}
for (int v : terminals) if (!seen[v]) return std::nullopt;
}
if (terminals.size() >= std::numeric_limits<int>::digits) throw std::length_error("SteinerTree terminals");
int states = int(1U << terminals.size());
if (std::size_t(states) > std::vector<Sum>().max_size() / std::size_t(n_)) throw std::length_error("SteinerTree states");
std::size_t count = std::size_t(states) * n_;
std::vector<Sum> dp(count, inf);
std::vector<int> trace;
if constexpr (Restore) trace.assign(count, -1);
bool dense = std::uint64_t(n_) * n_ <= 4 * std::uint64_t(edges_.size());
std::vector<unsigned char> used(dense ? n_ : 0);
for (int mask = 1; mask < states; ++mask) {
std::size_t offset = std::size_t(mask) * n_;
Sum *current = dp.data() + offset;
if (std::has_single_bit(unsigned(mask))) current[terminals[std::countr_zero(unsigned(mask))]] = 0;
else for (int part = (mask - 1) & mask; part > (mask ^ part); part = (part - 1) & mask) {
const Sum *left = dp.data() + std::size_t(part) * n_;
const Sum *right = dp.data() + std::size_t(mask ^ part) * n_;
for (int v = 0; v < n_; ++v) {
if (right[v] >= inf - left[v]) continue;
Sum next = left[v] + right[v];
if (next < current[v]) {
current[v] = next;
if constexpr (Restore) trace[offset + v] = -part - 1;
}
}
}
auto relax = [&](int v, Sum cost, auto push) {
for (auto [u, id] : graph[v]) {
Sum weight = Sum(edges_[id].cost);
if (weight >= inf - cost) continue;
Sum next = cost + weight;
if (next < current[u]) {
current[u] = next;
if constexpr (Restore) trace[offset + u] = id;
push(next, u);
}
}
};
if (dense) {
std::fill(used.begin(), used.end(), 0);
for (int iteration = 0; iteration < n_; ++iteration) {
int v = -1;
Sum cost = inf;
for (int u = 0; u < n_; ++u) if (!used[u] && current[u] < cost) cost = current[u], v = u;
if (v < 0 || (mask == states - 1 && cost >= current[root])) break;
used[v] = 1;
relax(v, cost, [](Sum, int) {});
}
} else {
shortest_path_detail::DistanceQueue<Sum> queue;
for (int v = 0; v < n_; ++v) if (current[v] < inf) queue.push(current[v], v);
while (!queue.empty()) {
auto [cost, v] = queue.pop();
if (cost != current[v]) continue;
if (mask == states - 1 && cost >= current[root]) break;
relax(v, cost, [&](Sum next, int u) { queue.push(next, u); });
}
}
}
Sum answer = dp[std::size_t(states - 1) * n_ + root];
if (!(answer < inf)) return std::nullopt;
Result result;
result.cost = answer;
if constexpr (Restore) {
UnionFind uf(n_);
std::vector<std::pair<int, int>> work{ {states - 1, root} };
while (!work.empty()) {
auto [mask, v] = work.back();
work.pop_back();
while (true) {
int step = trace[std::size_t(mask) * n_ + v];
if (step == -1) break;
if (step < -1) {
int part = -step - 1;
work.emplace_back(mask ^ part, v);
mask = part;
} else {
const auto &e = edges_[step];
if (!uf.same(e.from, e.to)) {
uf.merge(e.from, e.to);
result.edges.push_back(step);
}
v ^= e.from ^ e.to;
}
}
}
}
return result;
}
public:
explicit SteinerTree(int n = 0) : n_(n) { assert(0 <= n && n < std::numeric_limits<int>::max()); }
int size() const { return n_; }
int edge_count() const { return int(edges_.size()); }
void reserve(std::size_t m) {
assert(m <= std::size_t(std::numeric_limits<int>::max() / 2));
edges_.reserve(m);
}
int add_edge(int u, int v, Cost cost) {
assert(0 <= u && u < n_ && 0 <= v && v < n_ && cost >= 0);
assert(edges_.size() < std::size_t(std::numeric_limits<int>::max() / 2));
int id = edge_count();
edges_.push_back({u, v, cost});
return id;
}
Edge get_edge(int id) const { assert(0 <= id && id < edge_count()); return edges_[id]; }
const std::vector<Edge> &edges() const { return edges_; }
void clear() { edges_.clear(); }
std::optional<Result> solve(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
return run<true>(std::move(terminals), inf);
}
std::optional<Sum> minimum_cost(std::vector<int> terminals, Sum inf = std::numeric_limits<Sum>::max()) const {
auto result = run<false>(std::move(terminals), inf);
if (!result) return std::nullopt;
return result->cost;
}
};
#line 1 "components/fast_io.hpp"
#line 5 "components/fast_io.hpp"
#include <array>
#line 8 "components/fast_io.hpp"
#include <charconv>
#line 11 "components/fast_io.hpp"
#include <cstdio>
#include <cstring>
#line 15 "components/fast_io.hpp"
#include <string>
#include <string_view>
#line 18 "components/fast_io.hpp"
#if defined(__unix__) || defined(__APPLE__)
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#endif
namespace fast_io_detail { struct BulkInput; struct BulkOutput; }
class FastInput {
friend struct fast_io_detail::BulkInput;
static constexpr std::size_t capacity = 1 << 16;
FILE *file = nullptr;
std::unique_ptr<char[]> buffer;
const char *current = "", *end = current;
std::string scratch;
void *mapping = nullptr;
std::size_t mapped_size = 0;
bool refill() {
if (!file) return false;
std::size_t n = std::fread(buffer.get(), 1, capacity, file);
current = buffer.get();
end = current + n;
return n;
}
static const char *scan(const char *p, const char *end) {
while (end - p >= 8) {
std::uint64_t x;
std::memcpy(&x, p, 8);
if ((x - 0x2121212121212121ULL) & ~x & 0x8080808080808080ULL) break;
p += 8;
}
while (p != end && static_cast<unsigned char>(*p) > ' ') ++p;
return p;
}
public:
explicit FastInput(FILE *input = stdin) {
#if defined(__unix__) || defined(__APPLE__)
struct stat status;
int fd = fileno(input);
auto offset = ftello(input);
if (fd >= 0 && offset >= 0 && !fstat(fd, &status) && S_ISREG(status.st_mode) && status.st_size > offset) {
mapped_size = status.st_size;
mapping = mmap(nullptr, mapped_size, PROT_READ, MAP_PRIVATE, fd, 0);
if (mapping != MAP_FAILED) {
current = static_cast<const char *>(mapping) + offset;
end = static_cast<const char *>(mapping) + mapped_size;
return;
}
mapping = nullptr;
}
#endif
file = input;
buffer = std::make_unique_for_overwrite<char[]>(capacity);
}
explicit FastInput(std::string_view input) : current(input.empty() ? "" : input.data()), end(current + input.size()) {}
FastInput(const FastInput &) = delete;
FastInput &operator=(const FastInput &) = delete;
~FastInput() {
#if defined(__unix__) || defined(__APPLE__)
if (mapping) munmap(mapping, mapped_size);
#endif
}
std::string_view token() {
while (true) {
while (current != end && static_cast<unsigned char>(*current) <= ' ') ++current;
if (current != end) break;
if (!refill()) return {};
}
const char *begin = current;
current = scan(current, end);
if (current != end || !file) return {begin, std::size_t(current - begin)};
scratch.assign(begin, end);
while (refill()) {
current = scan(current, end);
scratch.append(buffer.get(), std::size_t(current - buffer.get()));
if (current != end) break;
}
return scratch;
}
template <class T>
bool read(T &value) {
if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) {
while (true) {
while (current != end && static_cast<unsigned char>(*current) <= ' ') ++current;
if (current != end) break;
if (!refill()) return false;
}
if constexpr (std::is_unsigned_v<T> && sizeof(T) == 4 && std::endian::native == std::endian::little) {
if (end - current >= 11) {
std::uint64_t x;
std::memcpy(&x, current, 8);
if (!(((x + 0x4646464646464646ULL) | (x - 0x3030303030303030ULL)) & 0x8080808080808080ULL)) {
x &= 0x0f0f0f0f0f0f0f0fULL;
x = (x * 10 + (x >> 8)) & 0x00ff00ff00ff00ffULL;
x = (x * 100 + (x >> 16)) & 0x0000ffff0000ffffULL;
std::uint64_t v = std::uint32_t(x * 10000 + (x >> 32));
int n = 8;
for (; n < 10 && static_cast<unsigned char>(current[n]) - unsigned('0') < 10; ++n)
v = v * 10 + (current[n] - '0');
if (static_cast<unsigned char>(current[n]) <= ' ' && v <= 0xffffffffULL) {
current += n;
value = T(v);
return true;
}
}
}
}
T parsed{};
auto result = std::from_chars(current, end, parsed);
if (result.ec == std::errc{} && (result.ptr != end ? static_cast<unsigned char>(*result.ptr) <= ' ' : !file)) {
current = result.ptr;
value = parsed;
return true;
}
}
auto s = token();
if (s.empty()) return false;
if constexpr (std::is_same_v<T, bool>) {
assert(s == "0" || s == "1");
value = s[0] == '1';
} else if constexpr (std::is_integral_v<T>) {
auto result = std::from_chars(s.data(), s.data() + s.size(), value);
assert(result.ec == std::errc{} && result.ptr == s.data() + s.size());
(void)result;
} else value = T(s);
return true;
}
};
class FastOutput {
friend struct fast_io_detail::BulkOutput;
inline static constexpr auto quads = [] {
std::array<std::array<char, 4>, 10000> table{};
for (int i = 0; i < 10000; ++i)
table[i] = {char('0' + i / 1000), char('0' + i / 100 % 10), char('0' + i / 10 % 10), char('0' + i % 10)};
return table;
}();
FILE *file;
std::unique_ptr<char[]> buffer = std::make_unique_for_overwrite<char[]>(1 << 16);
std::size_t capacity = 1 << 16, length = 0;
char *reserve(std::size_t n) {
if (n > capacity - length) {
if (!flush()) throw std::runtime_error("output failed");
if (n > capacity) {
std::size_t next = std::max(n, 2 * capacity);
buffer = std::make_unique_for_overwrite<char[]>(next);
capacity = next;
}
}
return buffer.get() + length;
}
public:
explicit FastOutput(FILE *output = stdout) : file(output) {}
FastOutput(const FastOutput &) = delete;
FastOutput &operator=(const FastOutput &) = delete;
~FastOutput() { flush(); }
bool flush() {
std::size_t offset = 0;
while (offset < length) {
auto n = std::fwrite(buffer.get() + offset, 1, length - offset, file);
if (!n) {
std::memmove(buffer.get(), buffer.get() + offset, length - offset);
length -= offset;
return false;
}
offset += n;
}
length = 0;
return std::fflush(file) == 0;
}
void write(char c) { *reserve(1) = c; ++length; }
void write(__uint128_t value) {
char digits[40];
char *end = digits + sizeof(digits), *begin = end;
do { *--begin = char('0' + value % 10); value /= 10; } while (value);
write(std::string_view(begin, end - begin));
}
void write(__int128_t value) {
__uint128_t magnitude = __uint128_t(value);
if (value < 0) write('-'), magnitude = 0 - magnitude;
write(magnitude);
}
void write(std::string_view s) {
char *out = reserve(s.size());
if (!s.empty()) std::memcpy(out, s.data(), s.size());
length += s.size();
}
template <class T> requires std::is_integral_v<T>
void write(T value) {
char *out = reserve(32);
if constexpr (std::is_same_v<T, bool>) *out = '0' + value, ++length;
else if constexpr (std::is_unsigned_v<T> && sizeof(T) == 4) {
char *p = out;
if (value >= 100000000) {
auto high = value / 100000000, low = value % 100000000;
p = std::to_chars(p, p + 2, high).ptr;
std::memcpy(p, quads[low / 10000].data(), 4);
std::memcpy(p + 4, quads[low % 10000].data(), 4);
p += 8;
} else if (value >= 10000) {
p = std::to_chars(p, p + 4, value / 10000).ptr;
std::memcpy(p, quads[value % 10000].data(), 4);
p += 4;
} else p = std::to_chars(p, p + 4, value).ptr;
length += p - out;
} else length += std::to_chars(out, out + 32, value).ptr - out;
}
template <class T> requires requires(const T &value, char *out) { value.decimal_capacity(); value.to_chars(out); }
void write(const T &value) {
char *out = reserve(value.decimal_capacity());
length += value.to_chars(out) - out;
}
template <class T>
void println(const T &value) { write(value); write('\n'); }
};
#line 4 "test/steiner_tree.test.cpp"
int main() {
FastInput input;
FastOutput output;
int n = 0, m = 0;
input.read(n), input.read(m);
SteinerTree<> graph(n);
graph.reserve(m);
for (int i = 0; i < m; ++i) {
int u = 0, v = 0;
std::int64_t w = 0;
input.read(u), input.read(v), input.read(w);
graph.add_edge(u, v, w);
}
int k = 0;
input.read(k);
std::vector<int> terminals(k);
for (int &v : terminals) input.read(v);
auto result = graph.solve(terminals);
assert(result);
output.write(result->cost), output.write(' '), output.write(result->edges.size()), output.write('\n');
for (std::size_t i = 0; i < result->edges.size(); ++i) {
if (i) output.write(' ');
output.write(result->edges[i]);
}
output.write('\n');
}