#include <bits/stdc++.h> #include "dreaming.h" using namespace std; constexpr int inf = 1e9; vector<bool> vis; vector<vector<pair<int, int>>> g; vector<int> dp1, dp2, res, nodes; void dfs_down(int u, int p) { nodes.push_back(u); vis[u] = 1; for (auto [v, w] : g[u]) { if (v == p) continue; dfs_down(v, u); if (dp1[v] + w > dp1[u]) { dp2[u] = dp1[u]; dp1[u] = dp1[v] + w; } else { dp2[u] = max(dp2[u], dp1[v] + w); } } res[u] = max(res[u], dp1[u]); } void dfs(int u, int p, int up) { res[u] = max(res[u], up); for (auto [v, w] : g[u]) { if (v == p) continue; int mx = 0; if (dp1[v] + w == dp1[u]) { mx = dp2[u]; } else { mx = dp1[u]; } dfs(v, u, max(up, mx) + w); } } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { g.resize(n); vis.resize(n); dp1.resize(n); dp2.resize(n); res.resize(n); for (int i = 0; i < m; i++) { int u = a[i], v = b[i], w = t[i]; g[u].push_back({v, w}); g[v].push_back({u, w}); } int ans = 0; vector<int> x; for (int i = 0; i < n; i++) { if (!vis[i]) { dfs_down(i, -1); dfs(i, -1, 0); int mn = inf; for (auto j : nodes) { ans = max(ans, res[j]); mn = min(mn, res[j]); } x.push_back(mn); for (auto j : nodes) { dp1[j] = dp2[j] = res[j] = 0; } nodes.clear(); } } sort(x.rbegin(), x.rend()); if (x.size() >= 2) { ans = max(ans, x[0] + x[1] + l); } if (x.size() >= 3) { ans = max(ans, x[1] + x[2] + 2 * l); } return ans; }