# RUNNING (PreDH 2021)

Apr 17th, 2021
1,212
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <cstdio>
3. #include <algorithm>
4. #include <vector>
6.
7. using namespace std;
8. using ld = long double;
9. using ll = long long;
10.
11. const int N = 1e5 + 5;
12. const int Inf = 1e9 + 7;
13. int n, x, y;
14. int dp[N];
15. int u[N], v[N], c[N], par[N];
17.
19.     cin >> n >> x >> y;
20.
21.     for(int i = 1; i < n; ++i){
22.         cin >> u[i] >> v[i] >> c[i];
25.     }
26. }
27.
28. void dfs(int V) {
30.         int i = V ^ u[z] ^ v[z];
31.         if(i != par[V]) {
32.             par[i] = V;
33.             dp[i] = min(dp[V], c[z]);
34.             dfs(i);
35.         }
36.     }
37. }
38.
39. void Solve(){
40.     dp[x] = Inf;
41.     par[x] = x;
42.     dfs(x);
43.
44.     int ans(dp[y]);
45.
46.     int k = y;
47.     while(par[k] != x) k = par[k];
48.
49.     int maxx(0), maxy(0), resy(0), resx(0);
50.
52.         int i = u[z] ^ x ^ v[z];
53.         if(i != k) maxx = max(maxx, c[z]);
54.         else resx = c[z];
55.     }
56.
58.         int i = u[z] ^ y ^ v[z];
59.         if(i != par[y]) maxy = max(maxy, c[z]);
60.         else resy = c[z];
61.     }
62.
63.     ans = max(ans, dp[y] + min(maxx, maxy));
64.     ans = max(ans, min(resx, resy + maxy));
65.     ans = max(ans, min(resx + maxx, resy));
66.     ans = max(ans, min(resx, resy));
67.
68.     cout << ans;
69. }
70.
71. int32_t main(){
72.     ios::sync_with_stdio(0);
73.     cin.tie(0);
74.     cout.tie(0);
75.
79.     }
80.
82.     Solve();
83. }
84.
RAW Paste Data