#include <bits/stdc++.h> #define ll long long #define task "cities" using namespace std; const int N = 2e5 + 16; int n, K, m, u, v; ll w; vector <int> critical; struct edge { int u, v; ll w; bool operator < (const edge &other) const { return w < other.w; } }; edge edgeList[N]; /* 4 3 6 1 3 4 1 2 4 1 3 9 1 4 6 2 3 2 2 4 5 3 4 8 */ /* 10 3 12 1 5 10 1 2 4 1 3 10 3 4 8 2 4 5 4 5 6 3 5 7 3 6 9 6 7 2 6 8 3 7 9 16 8 9 16 9 10 20 */ namespace sub5 { struct dsu { int parent[N], sz[N]; void makeSet(int k) { parent[k] = k; sz[k] = 1; } int findSet(int k) { if (k == parent[k]) { return k; } int p = findSet(parent[k]); parent[k] = p; return p; } bool unionSet(int a, int b) { a = findSet(a); b = findSet(b); if (a != b) { if (sz[a] < sz[b]) { swap(a, b); } parent[b] = a; sz[a] += sz[b]; return true; } return false; } }; dsu g1; vector <edge> need; ll mst; vector <int> adj[N]; int cnt, st[N], sparse[26][N << 2], h[N], f[N]; void dfs(int k, int p) { sparse[0][++cnt] = k; st[k] = cnt; for (auto v : adj[k]) { if (v == p) { continue; } h[v] = h[k] + 1; dfs(v, k); sparse[0][++cnt] = k; } } int lca(int u, int v) { int l = st[u], r = st[v]; if (l > r) { swap(l, r); } int k = __lg(r - l + 1); if (h[sparse[k][l]] < h[sparse[k][r - (1 << k) + 1]]) { return sparse[k][l]; } return sparse[k][r - (1 << k) + 1]; } void dpCalc(int k, int p) { for (auto v : adj[k]) { if (v == p) { continue; } dpCalc(v, k); f[k] += f[v]; } } void solve() { sort(edgeList + 1, edgeList + 1 + m); for (int i = 1; i <= n; i++) { g1.makeSet(i); } for (int i = 1; i <= m; i++) { u = edgeList[i].u; v = edgeList[i].v; w = edgeList[i].w; if (g1.unionSet(u, v)) { need.push_back({u, v, w}); mst += w; adj[u].push_back(v); adj[v].push_back(u); } } dfs(1, 1); for (int j = 1; j <= 20; j++) { for (int i = 1; i + (1 << j) - 1 <= cnt; i++) { if (h[sparse[j - 1][i]] < h[sparse[j - 1][i + (1 << (j - 1))]]) { sparse[j][i] = sparse[j - 1][i]; } else { sparse[j][i] = sparse[j - 1][i + (1 << (j - 1))]; } } } for (auto &x : need) { if (h[x.u] > h[x.v]) { swap(x.u, x.v); } } for (int i = 0; i < critical.size(); i++) { for (int j = i + 1; j < critical.size(); j++) { u = critical[i]; v = critical[j]; f[u]++; f[v]++; f[lca(u, v)] -= 2; } } dpCalc(1, 1); for (auto x : need) { if (f[x.v] == 0) { mst -= x.w; } } cout << mst; } } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> n >> K >> m; for (int i = 1; i <= K; i++) { cin >> u; critical.push_back(u); } for (int i = 1; i <= m; i++) { cin >> u >> v >> w; edgeList[i] = {u, v, w}; } sub5 :: solve(); return 0; }

cities.cpp: In function 'int main()':
cities.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~