#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]; int dfs2(int v, int p) { us[v] = true; multiset<int> q; if (p != -1) { q.insert(dp[v]); } for (pair<int, int> u : g[v]) { if (u.first == p) continue; q.insert(d[u.first] + u.second); } int ret = *(--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; ret = min(dfs2(u.first, v), ret); } return ret; } 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; } vector<int> w; for (int i = 0; i < N; ++i) { if (!us[i]) { dfs1(i, i); dp[i] = 0; w.push_back(dfs2(i, i)); } } sort(w.begin(), w.end()); reverse(w.begin(), w.end()); if (w.size() == 2) { return w[0] + w[1] + L; } else { return max(w[0] + w[1] + L, w[1] + w[2] + L + L); } }