#include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5+5; const int INF = 1e9; int dist[2][MAXN]; bool vis[MAXN]; vector<pair<int,int>> adj[MAXN]; vector<int> cr; int c = 0; void dfs(int x, int p, bool flag){ vis[x] = true; if (flag) cr.push_back(x); for (auto v : adj[x]){ auto [u, w] = v; if (u == p) continue; dist[c][u] = dist[c][x] + w; dfs(u,x,flag); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i<N; i++){ dist[0][i] = INF; dist[1][i] = INF; vis[i] = false; } for (int i = 0; i<M; i++){ int a = A[i]; int b = B[i]; int w = T[i]; adj[a].push_back({b,w}); adj[b].push_back({a,w}); } //dfs i -> 0 int overall = -1; vector<int> radd; for (int i = 0; i<N; i++){ if (!vis[i]){ dist[c][i] = 0; dfs(i,-1,1); int v = i; for (auto u : cr){ if (dist[c][u] > dist[c][v]){ v = u; } } dist[c][v] = 0; dfs(v,-1,0); int u = i; for (auto qq : cr){ if (dist[c][qq] > dist[c][u]){ u = qq; } } int diam = dist[0][u]; overall = max(overall, diam); c = 1; dist[c][u] = 0; dfs(u, -1, 0); c = 0; int bst = INF; int idx = -1; for (auto qq : cr){ int one = max(dist[0][qq], dist[1][qq]); if (one < bst){ bst = one; idx = qq; } } radd.push_back(bst); cr.clear(); } } sort(radd.begin(),radd.end()); reverse(radd.begin(), radd.end()); int k = radd.size(); if (k >= 2){ overall = max(overall,radd[0] + L + radd[1]); } if (k >= 3){ overall = max(overall,radd[1] + L + radd[2] + L); } for (int i = 0; i<N; i++) adj[i].clear(); return overall; }