#include <iostream> #include <vector> #include <set> #include <algorithm> #include "dreaming.h" using namespace std; const int N_MAX = 1e5 + 8; vector<pair<int, int>> g[N_MAX]; int d[N_MAX], dp[N_MAX]; void dfs1(int v, int p) { d[v] = 0; for (pair<int, int> u : g[v]) { if (u.first == p) continue; dfs1(u.first, v); d[v] = max(d[v], d[u.first] + u.second); } } bool us[N_MAX]; pair<int, int> dfs2(int v, int p) { us[v] = true; multiset<int> q; q.insert(dp[v]); for (pair<int, int> u : g[v]) { if (u.first == p) continue; q.insert(d[u.first] + u.second); } int mx, mn; mx = mn = *(--q.end()); for (pair<int, int> u : g[v]) { if (u.first == p) continue; q.erase(q.find(d[u.first] + u.second)); dp[u.first] = *(--q.end()) + u.second; q.insert(d[u.first] + u.second); } q.clear(); for (pair<int, int> u : g[v]) { if (u.first == p) continue; pair<int, int> ret = dfs2(u.first, v); mn = min(ret.first, mn); mx = max(ret.second, mx); } return { mn, mx }; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i < M; ++i) { g[A[i]].emplace_back(B[i], T[i]); g[B[i]].emplace_back(A[i], T[i]); } for (int i = 0; i < N; ++i) { us[i] = false; } int ans = 0; vector<int> w; for (int i = 0; i < N; ++i) { if (!us[i]) { dfs1(i, i); dp[i] = 0; pair<int, int> ret = dfs2(i, i); w.push_back(ret.first); ans = max(ans, ret.second); } } sort(w.begin(), w.end()); reverse(w.begin(), w.end()); if (w.size() >= 2) { ans = max(w[0] + w[1] + L, ans); } if (w.size() >= 3) { ans = max(ans, w[1] + w[2] + L + L); } return ans; }