fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  6. #define ll long long
  7. #define el "\n"
  8. #define fi first
  9. #define se second
  10. #define _ROOT_ int main()
  11. #define M 1000000007
  12. #define MAXN 100005
  13. #define INF (1ll<<30)
  14. #define NAME "TAITRONG"
  15. #define debug(a) cout << #a << " = " << a << endl;
  16. using namespace std;
  17.  
  18. struct edge {
  19.     ll u, v, w;
  20. };
  21.  
  22. ll n, m, s, t;
  23. vector<edge> edges;
  24. ll lab[MAXN];
  25.  
  26. ll find_set(ll v) {
  27.     if (lab[v] < 0) return v;
  28.     return lab[v] = find_set(lab[v]);
  29. }
  30.  
  31. bool union_sets(ll a, ll b) {
  32.     a = find_set(a);
  33.     b = find_set(b);
  34.     if(a == b ) return false ;
  35.     if (lab[a] > lab[b]) swap(a, b);
  36.     lab[a] += lab[b];
  37.     lab[b] = a;
  38.     return true ;
  39. }
  40.  
  41. bool check(ll val) {
  42.  
  43.     FOR(i, 1, n) lab[i] = -1;
  44.  
  45.     for (auto e : edges) {
  46.         if (e.w >= val) {
  47.             union_sets(e.u, e.v);
  48.         }
  49.     }
  50.     return find_set(s) == find_set(t);
  51. }
  52.  
  53. void init() {
  54.     cin >> n >> m >> s >> t ;
  55.     REP(i, m) {
  56.         ll u, v, w;
  57.         cin >> u >> v >> w;
  58.         edges.push_back({u, v, w});
  59.     }
  60. }
  61.  
  62. void solve() {
  63.     ll l = 1, r = 10000, ans = 0;
  64.     while(l <= r) {
  65.         ll mid = (l + r) / 2;
  66.         if (check(mid)) {
  67.             ans = mid;
  68.             l = mid + 1;
  69.         } else {
  70.             r = mid - 1;
  71.         }
  72.     }
  73.     cout << ans << el;
  74. }
  75.  
  76. _ROOT_ {
  77.     // freopen(NAME".inp" , "r" , stdin);
  78.     // freopen(NAME".out" , "w", stdout) ;
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);
  81.     cout.tie(0);
  82.     int t = 1;
  83.     // cin >> t;
  84.     while(t--) {
  85.         init();
  86.         solve();
  87.     }
  88.     return (0&0);
  89. }
  90.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
4 5 1 4
1 2 10
2 4 1
1 3 5
3 4 3
1 4 2
stdout
copy 
3
https://ideone.com/RENP3w
language:
C++14 (gcc 8.3)
created:
3 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!