pastebin

Paste Search Dynamic
Recent pastes
reverse all
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. typedef pair<int, int> ii;
  7. #define all(x) begin(x), end(x)
  8. #define sz(x) (int)(x).size()
  9. #define MASK(i) (1ll << (i))
  10. #define BIT(x, i) (((x) >> (i)) & 1ll)
  11. #define builtin_popcount __builtin_popcountll
  12. #define Times cerr <<"nTime: "<<clock()/(double)1000<<" sec"
  13. // cout << setprecision(0) << fixed << ans;
  14.  
  15. const int N = (int)1e5 + 5;
  16. const int Sz = (int)1e6 + 5;
  17. const int INF = (int)1e9;
  18. const int MOD = (int)1e9 + 7;
  19. /***------------------------- END ---------------------------***/
  20. int n, s, t, trace[105];
  21. bool vis[105];
  22. vector<ii> adj[105];
  23. vector<int> p;
  24.  
  25. void dfs(int u, int val) {
  26.         vis[u] = true;
  27.         for (auto it : adj[u]) {
  28.                 int v = it.se, c = it.fi;
  29.                 if (!vis[v] && c >= val) {
  30.                         trace[v] = u;
  31.                         dfs(v, val);
  32.                 }
  33.         }
  34. }
  35.  
  36. bool check(int x) {
  37.         memset(trace, 0, sizeof trace);
  38.         memset(vis, false, sizeof vis);
  39.         dfs(s, x);
  40.         if (!vis[t]) return false;
  41.         p.clear();
  42.        
  43.         int tmp = t;
  44.         while (tmp != s) {
  45.                 p.push_back(tmp);
  46.                 tmp = trace[tmp];
  47.         }
  48.         p.push_back(s);
  49.  
  50.         return true;
  51. }
  52.  
  53. #define TASK "DULICH"
  54. int main() {
  55.         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  56.        
  57.         cin >> n >> s >> t;
  58.        
  59.         int u, v, c, lo = 0, hi = 0;
  60.         while (cin >> u >> v >> c) {
  61.                 adj[u].push_back({c, v});
  62.                 hi = max(hi, c);
  63.         }
  64.        
  65.         while (lo <= hi) {
  66.                 int mid = (lo + hi) >> 1;
  67.                 if (check(mid)) lo = mid + 1;
  68.                 else hi = mid - 1;
  69.         }
  70.        
  71.         cout << lo - 1 << 'n';
  72.        
  73.         reverse(all(p));
  74.         for (int i = 0; i < sz(p) - 1; i++) cout << p[i] << "->";
  75.         cout << p.back();
  76.  
  77.         return 0;
  78. }
Parsed in 0.009 seconds