#include <bits/stdc++.h> #include "dreaming.h" using namespace std; using ll = long long; using P = pair<int, int>; #define all(x) x.begin(), x.end() #define rep(i, l, n) for (int i = l; i < (n); ++i) #define sz(x) (int)x.size() const char nl = '\n'; const int mod = 1e9+7; const int NMAX = 1e5+10; vector<P> g[NMAX]; int max_dis, endpoint, ok = 0; int dp[NMAX], vis[NMAX]; vector<int> members, W; void dfs(int node, int par, int dis) { // finding one endpoint of the diametr vis[node] = 1; if (dis > max_dis) max_dis = dis, endpoint = node; for (auto [v, w]: g[node]) if (v != par)dfs(v, node, dis+w); } void calc_dp(int node, int par, int dis) { // dp[nd] = max(dis(nd, a), dis(nd, b)), where a and b is endpoints of the diametr dp[node] = max(dp[node], dis); if(ok)members.push_back(node); for (auto [v, w]: g[node]) if (v != par)calc_dp(v, node, dis+w); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { rep(i, 0, M) g[A[i]].push_back(P(B[i], T[i])), g[B[i]].push_back(P(A[i], T[i])); int res = 0; int cnt = 0; rep(i, 0, N) { if (vis[i])continue; cnt += 1; max_dis = 0, endpoint = i; dfs(i, i, 0); int a = endpoint; max_dis = 0; dfs(a, a, 0); res = max(res, max_dis); int b = endpoint; ok = 1; calc_dp(a, a, 0); ok = 0; calc_dp(b, b, 0); int mn = 1e9; for (auto v: members)mn = min(mn, dp[v]); W.push_back(mn); members.clear(); } sort(W.rbegin(), W.rend()); if (sz(W) >= 2)res = max(res, W[0]+W[1]+L); if (sz(W) >= 3)res = max(res, W[1]+W[2]+2*L); return res; }