#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<pair<int, int>> adj[N]; // cout << "hi\n";
for(int i=0; i<M; i++){
adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]});
}
// get longest travel path of each node in each graph
// KEY: there's only one diameter path and the longest travel path of each node is ALWAYS to either endpoint
// just do DFS from x -> endp, endp -> (gets other endp) then 2 endps -> all, calculating along the way
// then find the min dist of each graph so when connecting using that node, it will ensure least weight
vector<bool> vis(N, false);
vector<int> dist(N, 0), connect;
for(int i=0; i<N; i++){
if(!vis[i]){
// normal DFSes (im gonna do iterative DFS for ts lmao)
stack<pair<pair<int, int>, int>> s; s.push({{-1, i}, 0});
int uu, vv, d = -1; // endpoints and diameter length
// find first endp
while(!s.empty()){
auto [p, t] = s.top(); s.pop();
auto [u, v] = p;
if(t > d){
d = t; uu = v;
}
for(auto [w, ww] : adj[v]){
if(u != w && !vis[w]) s.push({{v, w}, t + ww});
}
}
// find second endp & dist from first endp
s.push({{-1, uu}, 0}); d = -1;
while(!s.empty()){
auto [p, t] = s.top(); s.pop();
auto [u, v] = p;
if(t > d){
d = t; vv = v;
}
dist[v] = max(dist[v], t);
for(auto [w, ww] : adj[v]){
if(u != w && !vis[w]) s.push({{v, w}, t + ww});
}
}
// DFS to find dists
int least = int(1e9), c; s.push({{-1, vv}, 0}); // c = connecting point
while(!s.empty()){
auto [p, t] = s.top(); s.pop();
auto [u, v] = p; vis[v] = true;
dist[v] = max(dist[v], t);
if(dist[v] < least){
least = dist[v]; c = v;
}
// cout << "dist of " << v << " is " << dist[v] << '\n';
for(auto [w, ww] : adj[v]){
if(u != w && !vis[w]) s.push({{v, w}, t + ww});
}
}
// cout << "connecting point of " << i << " is at " << c << '\n';
connect.push_back(c);
}
}
// connect the optimal connecting points
for(int i=0; i<N-M-1; i++){
// cout << "connecting " << connect[i] << " with " << connect[i+1] << '\n';
adj[connect[i]].push_back({connect[i+1], L}); adj[connect[i+1]].push_back({connect[i], L});
}
int res = -1, endp, dd = -1;
stack<pair<pair<int, int>, int>> s; s.push({{-1, 0}, 0});
while(!s.empty()){
auto [p, t] = s.top(); s.pop();
auto [u, v] = p;
if(t > dd){
dd = t; endp = v;
}
for(auto [w, ww] : adj[v]){
if(u != w) s.push({{v, w}, t + ww});
}
}
// cout << endp << '\n';
s.push({{-1, endp}, 0});
while(!s.empty()){
auto [p, t] = s.top(); s.pop();
auto [u, v] = p;
res = max(res, t);
for(auto [w, ww] : adj[v]){
if(u != w) s.push({{v, w}, t + ww});
}
}
return res;
}
// g++ -O2 -o dreaming dreaming.cpp grader.c && dreaming.exe < dreaming.in
