fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. #define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  5. #define ll long long
  6. #define vi vector<ll>
  7. #define pb push_back
  8. #define F first
  9. #define S second
  10. #define all(v) (v).begin(),(v).end()
  11. #define pii pair<ll,ll>
  12. #define vii vector<pii>
  13. #define MOD 1000000007LL
  14. #define calc_fact(n) tgamma(n+1)
  15.  
  16. //disjoint set Union
  17.  
  18. ll find_set(ll x,vi& parent)
  19. {
  20.     if(parent[x]==-1)return x;
  21.  
  22.     return find_set(parent[x],parent);
  23. }
  24.  
  25. void union_set(ll x,ll y,vi& parent)
  26. {
  27.     ll xroot=find_set(x,parent),yroot=find_set(y,parent);
  28.     if(xroot!=yroot)
  29.     parent[yroot]=xroot;
  30. }
  31.  
  32. signed main()
  33. {
  34.     FIO;
  35.     ll t;
  36.     cin>>t;
  37.     while(t--){
  38.     ll n,m,ans=LONG_LONG_MAX;
  39.     cin>>n>>m;
  40.     vector<pii> adj[n];
  41.     vi parent(n,-1);
  42.     vector<pair<ll,pii>> edge;
  43.  
  44.     // Kruskal Algorithmn for maximum Spanning Tree
  45.  
  46.     for(ll i=0;i<m;i++)
  47.     {
  48.         ll a,b,c;
  49.         cin>>a>>b>>c;a--;b--;
  50.         edge.pb({c,{a,b}});
  51.     }
  52.     //sorting edge weight in decreasing order
  53.  
  54.     sort(edge.rbegin(),edge.rend());
  55.     for(ll i=0;i<m;i++)
  56.     {
  57.         ll x=find_set(edge[i].S.F,parent),y=find_set(edge[i].S.S,parent);
  58.         if(x!=y)
  59.         {
  60.             union_set(x,y,parent);
  61.             adj[edge[i].S.F].pb({edge[i].S.S,edge[i].F});
  62.             adj[edge[i].S.S].pb({edge[i].S.F,edge[i].F});
  63.         }
  64.     }
  65.     vector<bool> visited(n,false);
  66.  
  67.     //BFS
  68.  
  69.     queue<ll> q;
  70.     q.push(0);
  71.     while(!q.empty())
  72.     {
  73.         ll v=q.front();
  74.         q.pop();
  75.         for(ll u=0;u<adj[v].size();u++)
  76.         {
  77.             if(!visited[adj[v][u].F])
  78.             {
  79.                 visited[adj[v][u].F]=true;
  80.                 q.push(adj[v][u].F);
  81.                 ans=min(ans,adj[v][u].S);
  82.             }
  83.         }
  84.     }
  85.  
  86.     // if not reachable or graph is disconnected
  87.  
  88.     if(!visited[n-1])
  89.     ans=-1;
  90.     cout<<ans<<"\n";
  91.     }
  92. }
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
1
4 5
1 2 80
3 1 20
2 3 60
4 3 300
2 4 90
stdout
copy 
80
https://ideone.com/VY6D4f
language:
C++14 (gcc 8.3)
created:
3 years 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!