fork download
copy 
  1. #include <map>
  2.  
  3. #include <cmath> 
  4.  
  5. #include <queue>
  6.  
  7. #include <string>
  8.  
  9. #include <chrono>
  10.  
  11. #include <vector>
  12.  
  13. #include <fstream>
  14.  
  15. #include <iostream>
  16.  
  17. #include <algorithm>
  18.  
  19. using namespace std;
  20.  
  21. #define endl "\n"
  22.  
  23. #define int long long
  24.  
  25. #define ll long long
  26.  
  27. #define MASK(i) (1LL << (i))
  28.  
  29. #define BIT(x, i) (((x) >> (i)) & 1)
  30.  
  31. int n, m;
  32.  
  33. ll ans = 0;
  34.  
  35. int a, b, c;
  36.  
  37. const int Lim = 5e5+55;
  38.  
  39. int vl[Lim];
  40.  
  41. bool vs[Lim];
  42.  
  43. bool live[Lim];
  44.  
  45. int pr[Lim];
  46.  
  47. int N = 0;
  48.  
  49. struct edge{
  50.  
  51.     int u, v, w;
  52.  
  53. };
  54.  
  55. int find(int u) {
  56.  
  57.     if (pr[u] == u) return u;
  58.  
  59.     return pr[u] = find(pr[u]);
  60.  
  61. }
  62.  
  63. bool join(int u, int v) {
  64.  
  65.     int rootU = find(u);
  66.  
  67.     int rootV = find(v);
  68.  
  69.     if (rootU == rootV) return false;
  70.  
  71.     pr[rootU] = rootV;
  72.  
  73.     return true;
  74.  
  75. }
  76.  
  77. vector<pair<int,int>> adj[Lim];
  78.  
  79. vector<edge> adj2;
  80.  
  81. void input() {
  82.  
  83.     cin >> n >> m;
  84.  
  85.     cin >> a >> b >> c;
  86.  
  87.     for ( int i = 1; i <= m; i++ ) {
  88.  
  89.         int u, v, w;
  90.  
  91.         cin >> u >> v >> w;
  92.  
  93.         adj[u].push_back({v,w});
  94.  
  95.         adj[v].push_back({u,w});
  96.  
  97.     }
  98.  
  99. }
  100.  
  101. void dfs(int u) {
  102.  
  103.     live[u] = true;
  104.  
  105.     for (auto [v, w] : adj[u]) {
  106.  
  107.         if (!live[v]) {
  108.  
  109.             dfs(v);
  110.  
  111.             if (vs[v]) vs[u] = true;  
  112.  
  113.         }
  114.  
  115.     }
  116.  
  117. }
  118.  
  119. void solve() {
  120.  
  121.     vs[a] = true;
  122.  
  123.     vs[b] = true;
  124.  
  125.     vs[c] = true;
  126.  
  127.     dfs(a);
  128.  
  129.     for ( int i = 1; i <= n; i++ ) if ( vs[i] == true ) pr[i] = i;
  130.  
  131.     for ( int i = 1; i <= n; i++ ) {
  132.  
  133.         if ( vs[i] == true ) {
  134.  
  135.             for ( pair<int,int> j : adj[i] ) {
  136.  
  137.                 int k = j.first;
  138.  
  139.                 int w = j.second;
  140.  
  141.                 if (vs[i] && vs[k] && i < k) {
  142.  
  143.                     adj2.push_back({i, k, w});
  144.  
  145.                 }
  146.  
  147.             }
  148.  
  149.         }
  150.  
  151.     }
  152.  
  153.     sort(adj2.begin(), adj2.end(), [](edge a, edge b) {
  154.  
  155.         return a.w < b.w;
  156.  
  157.     });
  158.  
  159.     for (int i = 0; i < (int)adj2.size(); i++) {
  160.  
  161.         int u = adj2[i].u;
  162.  
  163.         int v = adj2[i].v;
  164.  
  165.         int w = adj2[i].w;
  166.  
  167.  
  168.         if (join(u, v)) ans += w;
  169.  
  170.     }
  171.  
  172.  
  173. }
  174.  
  175. void output() {
  176.  
  177.     cout << ans;
  178.  
  179. }
  180.  
  181. int32_t main() {
  182.  
  183.     ios_base::sync_with_stdio(0);
  184.     cin.tie(nullptr);
  185.  
  186.     if ( fopen("test_case.inp","r") ) {
  187.  
  188.         freopen("test_case.inp","r",stdin);
  189.         freopen("test_case.out","w",stdout);
  190.  
  191.     }
  192.  
  193.     input();
  194.  
  195.     solve();
  196.  
  197.     output();
  198.  
  199.     return 0;
  200.  
  201. }
  202.  
Success #stdin #stdout 0.01s 17784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/H5FCX5
language:
C++14 (gcc 8.3)
created:
8 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!