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.  
  14. //find_set
  15.  
  16. ll find_set(ll x,vi& parent)
  17. {
  18.     if(parent[x]==-1)return x;
  19.  
  20.     return find_set(parent[x],parent);
  21. }
  22.  
  23. // union_set
  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.  
  33. signed main()
  34. {
  35.     FIO;
  36.     ll t;
  37.     cin>>t;
  38.     while(t--){
  39.     ll n,m;
  40.     cin>>n>>m;
  41.  
  42.     vector<pii> adj[n];
  43.  
  44.     vi parent(n,-1);
  45.     vector<pair<ll,pii>> edge;
  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.     // Maximum Spanning Tree
  53.     sort(edge.rbegin(),edge.rend());
  54.     for(ll i=0;i<m;i++)
  55.     {
  56.         ll x=find_set(edge[i].S.F,parent),y=find_set(edge[i].S.S,parent);
  57.         if(x!=y)
  58.         {
  59.             union_set(x,y,parent);
  60.             adj[edge[i].S.F].pb({edge[i].S.S,edge[i].F});
  61.             adj[edge[i].S.S].pb({edge[i].S.F,edge[i].F});
  62.         }
  63.     }
  64.     if(find_set(0,parent)!=find_set(n-1,parent))
  65.     cout<<"-1\n";
  66.     else
  67.     {
  68.         queue<pii> q;vector<bool> visited(n,false);
  69.         q.push({0,LONG_LONG_MAX});
  70.         visited[0]=true;
  71.         while(!q.empty())
  72.         {
  73.             ll v=q.front().F,val=q.front().S;
  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,min(val,adj[v][u].S)});
  81.                     if(adj[v][u].F==n-1)
  82.                     {
  83.                         cout<<min(val,adj[v][u].S)<<"\n";
  84.                         goto h;
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.         h:;
  90.     }
  91.     }
  92. }
Success #stdin #stdout 0s 4312KB
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/ROmw60
language:
C++14 (gcc 8.3)
created:
4 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!