#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<pair<int, int>> voisins[100 * 1000];
bool estPasse[100 * 1000];
int diamDeb, diamFin, diamTaille = 0;
pair<int, int> calcDiam(int noeud, int parent = -1) {
estPasse[noeud] = true;
pair<int, int> melFeuille = {noeud, 0};
for(pair<int, int> voisin : voisins[noeud]) {
if(voisin.first == parent)
continue;
pair<int, int> resFeuille = calcDiam(voisin.first, noeud);
resFeuille.second += voisin.second;
if(resFeuille.second + melFeuille.second >= diamTaille) {
diamTaille = resFeuille.second + melFeuille.second;
diamDeb = resFeuille.first;
diamFin = melFeuille.first;
}
if(resFeuille.second > melFeuille.second) {
melFeuille = resFeuille;
}
}
return melFeuille;
}
bool calcChemin(int deb, int fin, vector<int>& chemin, int parent = -1) {
if(deb == fin)
return true;
for(pair<int, int> voisin : voisins[deb]) {
if(voisin.first == parent)
continue;
if(calcChemin(voisin.first, fin, chemin, deb)) {
chemin.push_back(voisin.second);
return true;
}
}
return false;
}
int travelTime(int nbVilles, int nbRoutes, int nouvTaille, int debs[], int fins[], int temps[]) {
for(int iRoute = 0;iRoute < nbRoutes;iRoute++) {
voisins[debs[iRoute]].push_back({fins[iRoute], temps[iRoute]});
voisins[fins[iRoute]].push_back({debs[iRoute], temps[iRoute]});
}
int diamMax = 0;
vector<int> rayons;
for(int iVille = 0;iVille < nbVilles;iVille++) {
if(estPasse[iVille])
continue;
diamTaille = 0;
diamDeb = diamFin = iVille;
calcDiam(iVille);
vector<int> chemin;
calcChemin(diamDeb, diamFin, chemin);
int somme = 0;
int rayon = diamTaille;
for(int val : chemin) {
somme += val;
rayon = min(rayon, max(somme, diamTaille - somme));
}
diamMax = max(diamMax, diamTaille);
rayons.push_back(-rayon);
}
sort(rayons.begin(), rayons.end());
if(rayons.size() == 1)
return diamMax;
if(rayons.size() == 2) {
return max(diamMax, nouvTaille - rayons[0] - rayons[1]);
}
return max(diamMax, max(nouvTaille - rayons[0] - rayons[1], 2 * nouvTaille - rayons[1] - rayons[2]));
}
