fork download 
  1. #include <bits/stdc++.h>
  2. #define NMAX 10005
  3. using namespace std;
  4. struct edge{
  5.      int u;
  6.      int v;
  7.      int w;
  8. };
  9. edge graph[NMAX];
  10. int n,m,s,t,minimum=INT_MAX;
  11. struct create{
  12.     int len;
  13.     vector<int> DSU,sizeDSU;
  14.     create(int _n):len(_n),DSU(len+1),sizeDSU(len+1,1)
  15.     {
  16.         for(int i=1;i<=len;i++)
  17.         {
  18.             DSU[i]=i;
  19.         }
  20.     };
  21.     int find_root(int u)
  22.     {
  23.         return (DSU[u]==u)?u:DSU[u]=find_root(DSU[u]);
  24.     }
  25.     bool join(int u ,int v)
  26.     {
  27.         int root_u=find_root(u);
  28.         int root_v=find_root(v);
  29.         if(root_u==root_v)
  30.         {
  31.             return false;
  32.         }
  33.         if(sizeDSU[root_u]<sizeDSU[root_v])
  34.         {
  35.             swap(root_u,root_v);
  36.         }
  37.         DSU[root_v]=root_u;
  38.         sizeDSU[root_u]+=sizeDSU[root_v];
  39.         return true;
  40.     }
  41.     bool check(int u ,int v)
  42.     {
  43.         return (find_root(u)==find_root(v))?1:0;
  44.     }
  45. };
  46. void process()
  47. {
  48.      cin>>n>>m>>s>>t;
  49.      create dsu(n);
  50.      for(int i=0;i<m;i++)
  51.      {
  52.          cin>>graph[i].u>>graph[i].v>>graph[i].w;
  53.      }
  54.      sort(graph,graph+m,[](edge &a,edge&b){ return a.w>b.w;});
  55.      for(int i=0;i<m;i++)
  56.      {
  57.          if(!dsu.check(s,t)&&dsu.join(graph[i].u,graph[i].v))
  58.          {
  59.              minimum=graph[i].w;
  60.          }
  61.      }
  62.      cout<<minimum;
  63. }
  64. int main()
  65. {
  66.     ios_base::sync_with_stdio(0);
  67.     cin.tie(0);
  68.     cout.tie(0);
  69.     freopen("TAITRONG.INP","r",stdin);
  70.     freopen("TAITRONG.OUT","w",stdout);
  71.     process();
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BgD8le
language:
C++14 (gcc 8.3)
created:
191 days ago
visibility:
secret

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!