fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e3 + 5;
  5. int n , m;
  6. int dist[N];
  7. vector < pair < int , int > > g[N];
  8. queue < int > q;
  9.  
  10.  
  11. void BFS(int start , int x)
  12. {
  13.    dist[start] = 0;
  14.    q.push(start);
  15.    while(!q.empty())
  16.    {
  17.       int u = q.front();
  18.       q.pop();
  19.       for(auto e: g[u])
  20.       {
  21.          int v = e.first;
  22.          int w = e.second;
  23.          if(dist[v] > dist[u] + 1
  24.          && w > x)
  25.          {
  26.             dist[v] = dist[u] + 1;
  27.             q.push(v);
  28.          }
  29.       }
  30.    }
  31. }
  32.  
  33. bool check(int x)
  34. {
  35.    for(int i = 1 ; i <= n ; i++)
  36.       dist[i] = 1e9;
  37.  
  38.    int vung = 0;
  39.    for(int i = 1 ; i <= n ; i++)
  40.       if(dist[i] == 1e9)
  41.       {
  42.          BFS(i , x);
  43.          vung++;
  44.          if(vung > 1)
  45.             return true;
  46.       }
  47.    return false;
  48. }
  49.  
  50. main()
  51. {
  52.    ios::sync_with_stdio(0);
  53.    cin.tie(0);
  54.    cin >> n >> m;
  55.    for(int i = 1 ; i <= m ; i++)
  56.    {
  57.       int u , v , w;
  58.       cin >> u >> v >> w;
  59.       g[u].push_back({v , w});
  60.       g[v].push_back({u , w});
  61.    }
  62.    int l = -1 , r = 1e3 , ans = -1;
  63.    while(l <= r)
  64.    {
  65.       int mid = (l + r) / 2;
  66.       if(check(mid) == true)
  67.       {
  68.          r = mid - 1;
  69.          ans = mid;
  70.       }
  71.       else
  72.          l = mid + 1;
  73.    }
  74.    cout << ans;
  75. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/sGKaMZ
language:
C++14 (gcc 8.3)
created:
15 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!