#include "dreaming.h" #include <bits/stdc++.h> using namespace std; int travelTime(int N, int M, int L, int A[], int B[], int T[]) { vector<vector<pair<int, long long>>> adj(N); for (int i = 0; i < M; i++) { adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]}); } vector<bool> vis(N, 0); vector<long long> depth(N); vector<vector<pair<long long, int>>> mxu(N); function<void(int, int, vector<int> &)> dfs = [&](int a, int p, vector<int> &curr) { vis[a] = 1; for (auto x : adj[a]) { if (x.first == p) continue; depth[x.first] = depth[a]+x.second; dfs(x.first, a, curr); mxu[a].push_back({mxu[x.first][0].first+x.second, x.first}); } sort(mxu[a].rbegin(), mxu[a].rend()); mxu[a].push_back({0, -1}); curr.push_back(a); }; function<long long(int, int, long long)> agg = [&](int a, int p, long long sum) -> long long { long long best = max(mxu[a][0].first, sum); for (auto x : adj[a]) { if (x.first == p) continue; long long aus = (mxu[a][0].second == x.first) ? mxu[a][1].first : mxu[a][0].first; aus = max(aus, sum)+x.second; best = min(best, agg(x.first, a, aus)); } return best; }; vector<long long> md; long long f = 0; for (int i = 0; i < N; i++) { if (vis[i]) continue; depth[i] = 0; vector<int> r; dfs(i, -1, r); md.push_back(agg(i, -1, 0)); int dm = i; for (int x : r) { if (depth[dm] < depth[x]) dm = x; } r.clear(); depth[dm] = 0; dfs(dm, -1, r); for (int x : r) { if (depth[dm] < depth[x]) dm = x; } f = max(depth[dm], f); } sort(md.rbegin(), md.rend()); if (md.size() > 1) f = max(f, md[0]+md[1]+L); if (md.size() > 2) f = max(f, md[1]+md[2]+2*L); return f; }