fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100005;
  6.  
  7. int n, m, Ans;
  8. vector<pair<int, int>> dsk[N];
  9. bool visited[N];
  10.  
  11. void DFS(int u, int limit) {
  12.  
  13.     /// mảng visited[u] = 1 khi mà đã tới thăm đỉnh này
  14.     /// = 0 khi chưa thăm
  15.  
  16.     visited[u] = true;
  17.  
  18.     for (pair<int, int> t : dsk[u]) {
  19.  
  20.         int v = t.first;
  21.         int len = t.second;
  22.  
  23.         if (len <= limit && visited[v] == false)
  24.             DFS(v, limit);
  25.     }
  26. }
  27.  
  28. int main() {
  29.     cin >> n >> m;
  30.  
  31.     for (int i = 1; i <= m; i++) {
  32.         int u, v, len;
  33.         cin >> u >> v >> len;
  34.  
  35.         dsk[u].push_back({v, len});
  36.         dsk[v].push_back({u, len});
  37.  
  38.     }
  39.  
  40.     int L = 1;
  41.     int R = 1e9;
  42.     int Ans;
  43.  
  44.     while (L <= R) {
  45.         int mid = (L + R) / 2;
  46.  
  47.         for (int i = 1; i <= n; i++)
  48.             visited[i] = false;
  49.  
  50.         DFS(1, mid);
  51.  
  52.         if (visited[n] == true) {
  53.             R = mid - 1;
  54.             Ans = mid;
  55.         }
  56.         else L = mid + 1;
  57.  
  58.     }
  59.  
  60.     cout << Ans;
  61.  
  62. }
  63.  
Success #stdin #stdout 0.01s 5888KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/OYmf13
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!