#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() class UFTree { std::vector par_; std::vector rank_; public: UFTree(int N) { init(N); } UFTree() {} ~UFTree() {} void init(int N) { par_.resize(N); rank_.resize(N, 0); for (int i = 0; i < N; ++i) par_[i] = i; } int find(int x) { if ( par_[x] == x ) return x; else return ( par_[x] = find(par_[x])); } void unite(int x, int y) { x = find(x); y = find(y); if ( x == y ) return; if ( rank_[x] < rank_[y] ) par_[x] = y; else { par_[y] = x; if ( rank_[x] == rank_[y] ) ++rank_[x]; } } bool same(int x, int y) { return (find(x) == find(y)); } int operator[](size_t i) { return find(i); } }; template class MinSteinerTree { public: using matrix = std::vector>; matrix graph_; MinSteinerTree() {} MinSteinerTree(int n) { init(n); } T inf() { return (1<<29); } void init(int n) { graph_.resize(n); for (int i = 0; i < n; ++i) graph_[i].resize(n,inf()); for (int i = 0; i < n; ++i) graph_[i][i] = 0; } void add(int u, int v, T c) { graph_[u][v] = graph_[v][u] = c; } T solve(const std::vector &t) { return solve(t, graph_); } T solve(const std::vector &t, const std::vector> &g) { const int n = g.size(); const int nt = t.size(); if (nt <= 1) return 0; matrix d(g); //最短距離 for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]); // opt[S][p] := S をターミナルとし p を含む最小シュタイナー木を作成するときのコスト matrix opt(1<(n, inf())); // 各ターミナルから直接つなげる部分を先に計算 for (int p = 0; p < nt; ++p) for (int q = 0; q < n; ++q) opt[1<>N>>M>>T; vector> edge; MinSteinerTree mst(N); REP(i,M) { int a,b,c; cin>>a>>b>>c; --a,--b; mst.add(a,b,c); edge.emplace_back(c,a,b); // sort のため cost を先頭に入れておく } vector t(T); REP(i,T) { int tmp; cin>>tmp; --tmp; t[i] = tmp; } if (T <= 14) cout< idx(N); // index 参照用 int k = 0; REP(v,N) { if (find(RANGE(t), v) != t.end()) idx[v] = -1; else idx[v] = k++; } int mincost = (1<<30); // T が大きいときは T を除いた残りの頂点のうちどれを使うかの 2^(N-T) 通りを全探索する。 // kruskal 法 sort(RANGE(edge)); // cost が小さい順に並べる // O(2^(N-T)*M) for (int R = 0; R < (1<<(N-T)); ++R) { const auto inf = (1<<30); UFTree uft(N); // O(N) vector used(N,false); int cost = 0; int nR; for (auto e : edge) { int a,b,c; int ia,ib; tie(c,a,b) = e; ia = idx[a]; ib = idx[b]; // 端点が t にも R にも含まれていないなら飛ばす if ( ia >= 0 && !((1<= 0 && !((1< mincost ) { cost = inf; break; } } // 出来上がった木が単連結になっているか確認 nR = 0; REP(v,N) { // 単連結か? if (used[v] && uft[t[0]] != uft[v]) cost = inf; if ((1<solve(); delete obj; return 0; } #endif