/* Telebe of Adicto && Mamedov yani AzeTurk810 I see humans but no humanity */ #include "dreaming.h" #include <algorithm> #include <assert.h> #include <functional> #include <iostream> #include <utility> #include <vector> // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); using ll = long long; using namespace std; #define ln '\n' #define INFi 1e9 #define INFll 1e18 // #include <algo.hpp> #ifdef ONPC #else #define dbg(...) #define dbg_out(...) #endif // #define int ll int travelTime(int N, int M, int L, int A[], int B[], int T[]) { vector<vector<pair<int, int>>> g(N); for (int i = 0; i < M; i++) { int &u = A[i]; int &v = B[i]; int &w = T[i]; g[u].push_back({v, w}); g[v].push_back({u, w}); } vector<int> dist(N, false), used(N, false), par(N, -1); int res = -1; function<void(int, int, int)> dfs = [&](int v, int pa, int dst) { dist[v] = dst; used[v] = true; par[v] = pa; if (pa == -1) res = -1; if (res == -1 || dst > dist[res]) { res = v; } for (const auto &[u, w] : g[v]) { if (u == pa) continue; dfs(u, v, dst + w); } }; // WARNING: dfs den evvel res = -1 elemelisen res = -1; vector<pair<int, int>> groups; for (int i = 0; i < N; i++) { if (used[i]) continue; res = -1; dfs(i, -1, 0); dfs(res, -1, 0); vector<int> path; int cur = res; while (cur != -1) { path.push_back(cur); cur = par[cur]; } reverse(path.begin(), path.end()); int p1 = 0, p2 = dist[res], ans = p2, ansv = path[0]; int tot = dist[res]; for (int i = 0; i < path.size(); i++) { p1 = dist[path[i]]; p2 = tot - dist[path[i]]; int cur = max(p1, p2); if (ans > cur) { ansv = path[i]; ans = cur; } } groups.push_back({ansv, ans}); } sort(groups.begin(), groups.end(), [&](auto l, auto r) { return l.second > r.second; }); // dbg(groups); for (int i = 1; i < groups.size(); i++) { const int &u = groups[0].first; const int &v = groups[i].first; g[u].push_back({v, L}); g[v].push_back({u, L}); } res = -1; dfs(0, -1, 0); dfs(res, -1, 0); dbg(groups); assert(groups.size() - 1 == N - 1 - M); // cout << dist[res] << ln; return dist[res]; } // Attack on titan<3 // Just Imaginary /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄ ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈ ⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀ ⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀ ⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ */