fork download 
  1. #include <bits/stdc++.h>
  2. #define el "\n"
  3. #define int long long
  4. #define mp make_pair
  5. #define lb lower_bound
  6. #define ub upper_bound
  7. #define fi first
  8. #define se second
  9. #define sz(x) ((int)(x).size())
  10. #define all(v) (v).begin(), (v).end()
  11. #define pb push_back
  12. #define prs(n) fixed << setprecision(n)
  13.  
  14. const int mod = 1e9 + 7;
  15. const int N = 4e3 + 5;
  16.  
  17. inline int gcd(int a, int b) {
  18.   if (b == 0) return a;
  19.   return gcd(b, a % b);
  20. }
  21. inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
  22.  
  23. using namespace std;
  24.  
  25. struct edges {
  26.   int u, v;
  27.   int w;
  28. };
  29.  
  30. int n, m;
  31. int par[N];
  32. vector<edges> adj;
  33.  
  34. int cmp (edges a, edges b) {
  35.   return a.w < b.w;
  36. }
  37.  
  38. int find (int u) {
  39.   return (par[u] == u) ? u : par[u] = find(par[u]);
  40. }
  41.  
  42. int join (int u, int v, int &a, int &b) {
  43.   u = find(u);
  44.   v = find(v);
  45.   if (u == v || (u == a && v ==b) || (u == b && v == a)) return 0;
  46.   if (u == a) par[v] = a;
  47.   else if (u == b) par[v] = b;
  48.   else if (v == a) par[u] = a;
  49.   else if (v == b) par[u] = b;
  50.   else par[v] = u;
  51.   return 1;
  52. }
  53.  
  54. signed main() {
  55.   ios_base::sync_with_stdio(false);
  56.   cin.tie(0);
  57.   cout.tie(0);
  58.  
  59. #ifndef ONLINE_JUDGE
  60.   freopen("test.inp", "r", stdin);
  61.   freopen("test.out", "w", stdout);
  62. #endif
  63.  
  64.   cin >> n >> m;
  65.   for (int i = 1, u, v, w; i <= m; i++) {
  66.     cin >> u >> v >> w;
  67.     adj.pb({u, v, w});
  68.   }
  69.  
  70.   sort(all(adj), cmp);
  71.  
  72.   int q;
  73.   cin >> q;
  74.   while(q--) {
  75.     int u, v;
  76.     cin >> u >> v;
  77.  
  78.     for (int i = 1; i <= n; i++)
  79.       par[i] = i;
  80.  
  81.     int res = 0;
  82.     int nodes = 2;
  83.     for (int i = 0; i < m; i++) {
  84.       if (nodes == n) break;
  85.       edges e = adj[i];
  86.       if (join(e.u, e.v, u, v)) {
  87.         res += e.w;
  88.         nodes++;
  89.       }
  90.     }
  91.     cout << res << el;
  92.   }
  93.  
  94.   return 0;
  95. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
6 8
1 2 4
1 3 3
1 4 4
1 5 2
2 4 6
3 5 3
3 4 4
4 6 5
2
4 5
6 4
stdout 
14
13
https://ideone.com/t05J5J
language:
C++14 (gcc 8.3)
created:
6 days 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!