#include #include #include #include namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } int xorval() const { return from ^ to; } }; Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} Graph(int n, const std::vector>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i static Graph Input(Cin& cin, int n, bool undirected, int m, bool offset = 0){ Graph res(n, undirected, m); for(int i=0; i> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i induce(int num, const std::vector& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i indexV(n), newV(num); for(int i=0; i= 0) indexV[i] = newV[mapping[i]]++; std::vector res; res.reserve(num); for(int i=0; i= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray getEdgeIndexArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i::Construct(numVertices(), src); } CsrArray getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray getAdjacencyArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray::Construct(numVertices(), src); } CsrArray getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector m_e; bool m_isUndir; }; } // namespace nachia namespace nachia { struct DsuFast{ private: std::vector w; public: DsuFast(int n = 0) : w(n, -1) {} int leader(int u){ if(w[u] < 0) return u; return w[u] = leader(w[u]); } int operator[](int u){ return leader(u); } int merge(int u, int v){ u = leader(u); v = leader(v); if(u == v) return u; if(-w[u] < -w[v]) std::swap(u, v); w[u] += w[v]; w[v] = u; return u; } int size(int u){ return -w[leader(u)]; } bool same(int u, int v){ return leader(u) == leader(v); } }; } // namespace nachia #include namespace nachia{ template struct MultipleTimeDijkstra{ private: template using nega_queue = std::priority_queue, std::greater>; struct IncidentEdge{ int to; int e; Weight w; }; std::vector> inci; int n; int m; Weight inf; public: MultipleTimeDijkstra( Graph _graph, std::vector _weight, Weight _inf ) : n(_graph.numVertices()) , m(_graph.numEdges()) , inf(_inf) { inci.resize(n); for(int e=0; e solve(std::vector& w){ if(n == 0) return {}; std::vector res(n, -1); if(m/n <= 5){ std::vector vis(n, 0); for(int t=0; t> que; for(int v=0; v terminals; std::vector weight; Weight inf; std::vector>> dp; private: template using nega_queue = std::priority_queue, std::greater>; public: MinimumSteinerTree( Graph _graph, std::vector _terminals, std::vector _weight, Weight _inf ) : graph(std::move(_graph)) , terminals(std::move(_terminals)) , weight(std::move(_weight)) , inf(_inf) { int n = graph.numVertices(); int m = graph.numEdges(); int k = int(terminals.size()); dp.assign(1<>(n, std::make_pair(-m-1, inf))); auto zero = Weight(0); for(int i=0; i(graph, weight, inf); auto check = [&](int i, int v, int pre, Weight w){ if(w < dp[i][v].second) dp[i][v] = { pre, w }; }; for(int i=0; i<(1< F(n); for(int v=0; v= 0) dp[i][v] = { -P[v] - 1, F[v] }; } for(int kk=0; kk0; j=((j-1)&~i)) for(int v=0; v std::vector MinimumSteinerTreeExhaustiveMstMethod( const Graph& graph, const std::vector& weight, const std::vector& excluded ){ assert(excluded.size() <= 30); struct Edge { int u; int v; int e; Weight w; }; int n = graph.numVertices(); int m = graph.numEdges(); int k = excluded.size(); std::vector edges(m); for(int e=0; e is_ex(n); std::pair anslight = { Weight(0), -1 }; for(int f=0; f<(1<> i) & 1; exc -= q; is_ex[excluded[i]] = q; } DsuFast dsu(n); Weight wsum = Weight(0); int cnt = 0; for(auto& e : edges){ if(is_ex[e.u] || is_ex[e.v]) continue; if(dsu.same(e.u, e.v)) continue; dsu.merge(e.u, e.v); cnt++; wsum += e.w; } if(cnt != exc) continue; if(f == 0 || wsum < anslight.first) anslight = { wsum, f }; } std::vector selectedEdges; { int f = anslight.second; for(int i=0; i> i) & 1); DsuFast dsu(n); for(auto& e : edges){ if(is_ex[e.u] || is_ex[e.v]) continue; if(dsu.same(e.u, e.v)) continue; dsu.merge(e.u, e.v); selectedEdges.push_back(e.e); } } return selectedEdges; } } // namespace nachia #include #include #include #include int main(){ using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, T; cin >> N >> M >> T; nachia::Graph graph(N, true); vector weight; for(int i=0; i> u >> v >> c; u--; v--; graph.addEdge(u,v); weight.push_back(c); } vector terminals(T); for(int t=0; t> a; terminals[t] = a-1; } if(T <= 16){ auto st = nachia::MinimumSteinerTree(graph, terminals, weight, 1001001001001); cout << st.minWeight((1< mask(N); for(int t : terminals) mask[t] = 1; vector ex; for(int i=0; i