#include "dreaming.h" #include <bits/stdc++.h> using namespace std; vector<int> sr[100002]; void ff(vector<pair<int, int>> ap[], int cur, int par, int g) { sr[g].push_back(cur); for (auto& [p, w] : ap[cur]) { if (p == par) continue; ff(ap, p, cur, g); } } vector<int> mn(100005, -1); void dij(vector<pair<int, int>> ap[], int n, int s, int g) { for (auto& p : sr[g]) mn[p] = 2e9; mn[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({mn[s], s}); while (pq.size()) { auto [w, u] = pq.top(); pq.pop(); //if (mn[u] < w) continue; for (auto& [v, d] : ap[u]) { if (mn[v] > w + d) { mn[v] = w + d; pq.push({mn[v], v}); } } } //for (auto& p : sr[g]) cout << mn[p] << ' '; //cout << '\n'; } int findc(vector<pair<int, int>> ap[], int n, int s, int g) { dij(ap, n, s, g); int l = s; for (auto& p : sr[g]) { //cout << mn[p] << ' '; if (mn[p] > mn[l]) l = p; } //cout << mn[l] << ' '; dij(ap, n, l, g); int r = l; for (auto& p : sr[g]) { if (mn[p] > mn[r]) r = p; } vector<int> lm(100005); for (auto& p : sr[g]) lm[p] = mn[p]; dij(ap, n, r, g); int md = 2e9; for (auto& p : sr[g]) { md = min(md, max(lm[p], mn[p])); } return md; } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { vector<pair<int, int>> ap[n + 1]; for (int i = 0; i < m; i++) { ap[A[i]].push_back({B[i], T[i]}); ap[B[i]].push_back({A[i], T[i]}); } int g = 0; vector<int> arr; for (int i = 0; i < n; i++) { if (mn[i] == -1) { ff(ap, i, -1, ++g); int val = findc(ap, n, i, g); arr.push_back(val); } } sort(arr.rbegin(), arr.rend()); //for (auto& p : arr) cout << p << ' '; //cout << '\n'; int ans; if (arr.size() == 1) ans = arr[0]; else if (arr.size() <= 2) ans = arr[0] + arr[1] + l; else ans = max(arr[0] + arr[1] + l, l * 2 + arr[1] + arr[2]); return ans; }