fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "test"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 1e4 + 5;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37.  
  38. int n, m;
  39. tuple<int, int, int> Canh[N];
  40. vector<int> dsk[N];
  41. bool visited[N];
  42.  
  43. inline void Read_Input() {
  44.     cin >> n >> m;
  45.  
  46.     for (int i = 1; i <= m; i++) {
  47.         int u, v, w;
  48.         cin >> u >> v >> w;
  49.         Canh[i] = {u, v, w};
  50.     }
  51. }
  52.  
  53. void dfs(int u, int p) {
  54.     visited[u] = true;
  55.     for (int v : dsk[u])
  56.         if (v != p)
  57.             dfs(v, u);
  58. }
  59.  
  60. bool Check(int val) {
  61.     /// B2 : tạo đồ thị mới với những cạnh có trọng số <= x
  62.  
  63.     /// Bắt đầu làm là chưa có gì
  64.     FOR(i, 1, n)
  65.         visited[i] = false, dsk[i].clear();
  66.  
  67.     FOR(i, 1, m) {
  68.         auto[u, v, w] = Canh[i];
  69.  
  70.         if (w <= val) {
  71.             dsk[u].push_back(v);
  72.             dsk[v].push_back(u);
  73.         }
  74.     }
  75.  
  76.     dfs(1, 1);
  77.  
  78.     if (visited[n] == true) return true;
  79.     return false;
  80. }
  81.  
  82. inline void Solve() {
  83.     /// B1 : chặt nhị phân giá trị x để kiếm tra
  84.  
  85.     int l = 1, r = 1e9;
  86.     int Ans = -1;
  87.  
  88.     while (l <= r) {
  89.         int mid = (l + r) / 2;
  90.  
  91.         if (Check(mid) == true) {
  92.             /// Check gia tri 5 = dung
  93.  
  94.             /// [5, 6, 7 ... , 1e9] = dung
  95.  
  96.             /// [1, 4]
  97.  
  98.             r = mid - 1;
  99.             Ans = mid;
  100.         }
  101.         else l = mid + 1;
  102.     }
  103.  
  104.     cout << Ans;
  105.  
  106. }
  107.  
  108. Ti20_ntson {
  109. //    freopen(TASK".INP","r",stdin);
  110. //    freopen(TASK".OUT","w",stdout);
  111.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  112.     int T = 1;
  113. //    cin >> T;
  114.     while (T -- ) {
  115.         Read_Input();
  116.         Solve();
  117.     }
  118. }
  119.  
  120.  
  121.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/lQc0mS
language:
C++14 (gcc 8.3)
created:
3 hours 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!