#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define sz(x) (int)x.size()
#define pii pair<int, int>
#define int long long
using namespace std;
const int N = 3e5;
vector<pii> aretes[N];
bool vu[N][3];
int dists[N][3];
int nNoeuds, nAretes;
vector<int> cc;
void calcDist(int noeud, int distCur, int step){
vu[noeud][step] = true;
dists[noeud][step] = distCur;
if (step == 0)
cc.pb(noeud);
for (pii arete : aretes[noeud]){
if (vu[arete.first][step]) continue;
calcDist(arete.first, distCur + arete.second, step);
}
}
pii calcDiametre(int root){
cc = {};
calcDist(root, 0, 0);
/* cout << "cc " << root << endl;
for (int noeud : cc)
cout << noeud << " ";
cout << endl;*/
int ext1 = -1;
for (int noeud : cc){
if (ext1 == - 1 || dists[noeud][0] > dists[ext1][0])
ext1 = noeud;
}
calcDist(ext1, 0, 1);
int ext2 = -1;
for (int noeud : cc){
if (ext2 == - 1 || dists[noeud][1] > dists[ext2][1])
ext2 = noeud;
}
int mid = -1, res;
calcDist(ext2, 0, 2);
for (int noeud : cc){
if (mid == -1 || max(dists[noeud][1], dists[noeud][2]) < res)
mid = noeud, res = max(dists[noeud][1], dists[noeud][2]);
}
/*
for (int t = 1; t <= 2; ++t){
for (int nod = 0; nod < nNoeuds; ++nod)
cout << dists[nod][t] << " ";
cout << endl;
}
cout << "----------" << endl;
cout << "mid " << mid << endl;*/
return {res, mid};
}
signed travelTime(signed n, signed m, signed POIDS, signed A[], signed B[], signed T[]) {
nNoeuds = n; nAretes = m;
for (int iArete = 0; iArete < nAretes; ++iArete){
aretes[A[iArete]].pb({B[iArete], T[iArete]});
aretes[B[iArete]].pb({A[iArete], T[iArete]});
}
vector<pii> roots;
for (int noeud = 0; noeud < nNoeuds; ++noeud){
if (vu[noeud][0]) continue;
// cout << "NOEUD " << noeud << endl;
roots.pb(calcDiametre(noeud));
}
sort(all(roots));
set<int> potentiels = {roots[0].second, roots[sz(roots) - 1].second};
if (sz(roots) >= 2)
potentiels.insert(roots[sz(roots) - 2].second);
int minDiametre = 1e18;
for (int milieu : potentiels){
for (pii cc : roots){
int root = cc.second;
if (milieu != root){
aretes[milieu].pb({root, POIDS});
aretes[root].pb({milieu, POIDS});
}
}
for (int noeud = 0; noeud < nNoeuds; ++noeud)
for (int i = 0; i < 3; ++i)
vu[noeud][i] = false;
pii inutile = calcDiametre(milieu);
int diametre = 0;
for (int noeud = 0; noeud < nNoeuds; ++noeud)
for (int i = 0; i < 3; ++i)
chmax(diametre, dists[noeud][i]);
chmin(minDiametre, diametre);
for (pii cc : roots){
int root = cc.second;
if (milieu != root){
aretes[milieu].pop_back();
aretes[root].pop_back();
}
}
}
return (int)minDiametre;
}
