fork download 
  1. #include <bits/stdc++.h>
  2. #define FNAME "ROAD"
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXN = (int)2e5 + 5;
  6. const int LIM = (int)1e5 + 1;
  7. const long long MOD = (long long)1e13 + 15092007;
  8. #define xd '\n' 
  9. #define fi first
  10. #define se second
  11. const long long base = (long long)256;
  12. const long long INF = (long long)1e10;
  13. template<class X, class Y> bool minimize(X &a, Y b) {if(a>b){a=b;return true;}return false;};
  14. template<class X, class Y> bool maximize(X &a, Y b) {if(a<b){a=b;return true;}return false;};
  15. const int LOG = 19;
  16.  
  17. void HuuThien() {
  18.     ios_base::sync_with_stdio(0);
  19.     cin.tie(0); cout.tie(0);
  20.     if (fopen(FNAME".inp", "r")) {
  21.         freopen(FNAME".inp", "r", stdin);
  22.         freopen(FNAME".out", "w", stdout);
  23.     }
  24. }
  25.  
  26. struct edges{
  27.     int u, v;
  28.     long long w;
  29.     int eID;
  30. };
  31.  
  32. int parent[MAXN], Size[MAXN];
  33. bool visited[MAXN];
  34. int n, m, q, p;
  35. vector<edges> Edges;
  36.  
  37. void makeset(int n) {
  38.     for(int i = 1; i <= n ; i++) {
  39.         Size[i] = 1;
  40.         parent[i] = i;
  41.     }
  42. }
  43.  
  44. int find(int u) {
  45.     if(u == parent[u]) return u;
  46.     return parent[u] = find(parent[u]);
  47. }
  48.  
  49. void Union(int a, int b) {
  50.     a = find(a);
  51.     b = find(b);
  52.     if(a != b) {
  53.         if(Size[a] < Size[b]) swap(a, b);
  54.         Size[a] += Size[b];
  55.         parent[b] = a;
  56.     }
  57. }
  58.  
  59. void Init() {
  60.     cin >> n >> m;
  61.     makeset(n);
  62.     for(int i = 1; i <= m ; i++) {
  63.         int u, v, w;
  64.         cin >> u >> v >> w;
  65.         Edges.push_back({u, v, w, i});
  66.     }
  67. }
  68.  
  69. vector<int> needed;
  70. vector<pair<int, int>> banned;
  71.  
  72. bool cmp(edges a, edges b) {
  73.     return a.w < b.w;
  74. }
  75.  
  76. void Solve() {
  77.     int cnt = 0;
  78.     long long ans = 0;
  79.     cin >> q;
  80.     for(int i = 1; i <= q ; i++) {
  81.         int node;
  82.         cin >> node;
  83.         needed.push_back(node);
  84.     }
  85.  
  86.     cin >> p;
  87.     for(int i = 1; i <= p ; i++) {
  88.         int x, y;
  89.         cin >> x >> y;
  90.         if(x > y) swap(x, y);
  91.         banned.push_back({x, y});
  92.     }
  93.  
  94.     sort(banned.begin(), banned.end());
  95.  
  96.     for(pair<int, int> pe : banned) {
  97.         int x = pe.first, y = pe.second;
  98.         edges kx = Edges[x - 1];
  99.         edges ky = Edges[y - 1];
  100.         kx.eID = ky.eID = min(kx.eID, ky.eID);
  101.         Edges[x - 1] = kx;
  102.         Edges[y - 1] = ky;
  103.     }
  104.  
  105.     for(int node : needed) {
  106.         edges k = Edges[node - 1];
  107.         visited[k.eID] = true; 
  108.         Union(k.u, k.v);
  109.         ans += k.w;
  110.         cnt++;
  111.     }
  112.  
  113.     sort(Edges.begin(), Edges.end(), cmp);
  114.  
  115.     for(edges e : Edges) {
  116.         if(!visited[e.eID]) {
  117.             visited[e.eID] = true;
  118.             if(find(e.u) != find(e.v)) {
  119.                 ans += e.w;
  120.                 cnt++;
  121.                 Union(e.u, e.v);
  122.             }
  123.         }
  124.     }
  125.  
  126.     if(cnt == n - 1) {
  127.         cout << ans;
  128.     } else {
  129.         cout << -1;
  130.     }
  131. }
  132.  
  133. signed main() {
  134.     HuuThien();
  135.     Init();
  136.     Solve();
  137.     return 0;
  138. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/ABaL4M
language:
C++ (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!