#include <bits/stdc++.h> #include "dreaming.h" using namespace std; const int N = 1e5+5; int ans; int fix[N]; vector <int> roots; vector <vector<pair<int,int>>> v(N); int d[N]; int d1[N]; int d2[N]; vector <int> res; void dfs(int x) { res.push_back(x); fix[x] = 1; for (auto [to,w]:v[x]) { if (fix[to]) continue; d[to] = d[x] + w; dfs(to); } } void dfs1(int x, int p) { for (auto [to,w]:v[x]) { if (to == p) continue; d1[to] = d1[x] + w; dfs1(to,x); } } void dfs2(int x, int p) { for (auto [to,w]:v[x]) { if (to == p) continue; d2[to] = d2[x] + w; dfs2(to,x); } } int get(int x, int n) { res.clear(); dfs(x); int node1 = x; for (auto i:res) { if (d[node1] < d[i]) node1 = i; } dfs1(node1,node1); int node2 = x; for (auto i:res) { if (d1[node2] < d1[i]) node2 = i; } dfs2(node2,node2); int mn = INT_MAX; for (auto i:res) { mn = min(mn,max(d1[i],d2[i])); } return mn; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { ans = 0; for (int i = 0; i < M; i++) { v[A[i]].push_back({B[i],T[i]}); v[B[i]].push_back({A[i],T[i]}); } for (int i = 0; i < N; i++) { if (fix[i]) continue; roots.push_back(get(i,N)); } sort(roots.begin(),roots.end(),greater<int>()); if (roots.size() >= 2) { ans = max(ans, roots[0] + roots[1] + L); } if (roots.size() > 2) { ans = max(ans,roots[1]+roots[2]+2*L); } return ans; }