#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<bool> vis, dvis;
vector<int> diapath, diaedges;
void getpath(int a, int b, int N, vector<int> path = {}, vector<int> edges = {}){
path.push_back(a);
dvis[a] = true;
if(a == b){
diapath = path;
diaedges = edges;
return;
}
edges.push_back(0);
for(pair<int, int> i : adj[a]){
if(!dvis[i.first]){
edges[edges.size()-1] = i.second;
getpath(i.first, b, N, path, edges);
}
}
}
int diameter(int node, int N){
diapath.clear(), diaedges.clear();
int a = 0, b = 0, dist = 0;
dvis = vis;
queue<pair<int, int>> q;
vector<int> dia(N, -1), edges(N), parent(N);
q.push({node, 0});
while(!q.empty()){
pair<int, int> val = q.front();
q.pop();
if(dvis[val.first]) continue;
for(pair<int, int> i : adj[val.first]){
if(!dvis[i.first]){
q.push({i.first, i.second + val.second});
if(i.second + val.second > dist){
a = i.first;
dist = i.second + val.second;
}
}
}
dvis[val.first] = true;
}
q.push({a, 0});
dvis = vis, dist = 0;
dia[0] = a;
while(!q.empty()){
pair<int, int> val = q.front();
q.pop();
if(dvis[val.first]) continue;
for(pair<int, int> i : adj[val.first]){
if(!dvis[i.first]){
q.push({i.first, i.second + val.second});
if(i.second + val.second > dist){
b = i.first;
dist = i.second + val.second;
}
}
}
dvis[val.first] = true;
}
dvis = vis;
getpath(a, b, N);
vis = dvis;
return dist;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
int ret = 0, bigcenter = 0, maxdia = 0;
vector<int> centers;
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]});
}
vis.assign(N, false);
for(int i = 0; i < N; i++){
if(!vis[i]){
int dialength = diameter(i, N);
vis[i] = true;
int c = i, c1 = i, c2 = i, w1 = 0, w2 = 0;
if(dialength > 0){
cerr << "FORWARD:\n";
for(int j = 0; w1 <= dialength / 2; j++){
cerr << w1 << ' ' << dialength/2 << endl;
c1 = diapath[j];
if(j-1 >= 0) w1 += diaedges[j-1];
}
cerr << endl << "BACKWARD:\n";
for(int j = diapath.size() - 1; w2 <= dialength / 2; j--){
cerr << w2 << ' ' << dialength/2 << endl;
c2 = diapath[j];
if(j < diaedges.size()) w2 += diaedges[j];
}
if(w1 > w2) c = c2;
else c = c1;
cerr << endl << c1 << ' ' << c2 << endl;
}
if(dialength > maxdia){
bigcenter = c;
maxdia = dialength;
}
centers.push_back(c);
}
}
for(int i : centers){
cerr << i << ' ';
if(i != bigcenter){
adj[i].push_back({bigcenter, L});
adj[bigcenter].push_back({i, L});
}
}
cerr << endl;
vis.assign(N, false);
return diameter(0, N);
}
