#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
const ll INF = 1e15;
const ll NMAX = 1e5+5;
struct Vertex {
int id, parent;
ll pdist;
Vertex () {}
Vertex (int x) { id = x; }
};
struct Graph {
vector <Vertex> V;
vector <pair <ll, int> > Adj[NMAX];
vector <bool> vis;
int excluded = -1, sze;
Graph () {}
Graph (int s) {
sze = s;
V.resize(sze);
for (int i=0; i<s; i++) V[i] = Vertex(i);
}
// Hace una DFS y devuelve el nodo más lejano
pair <ll,int> DFS(int o) {
//cerr << "Entrando a DFS..." << endl;
vector <ll> dist;
stack <pair <int,int> > to;
dist.resize(sze);
vis.resize(sze);
for (int i=0; i<sze; i++) dist[i] = INF, vis[i] = false;
// Hace la DFS
to.push({0LL, o});
dist[o] = 0;
while (!to.empty()) {
pair <int, ll> curr = to.top();
//cerr << "Visitando " << curr.ss << " (distancia acc " << curr.ff << ")" << endl;
to.pop();
dist[curr.ss] = curr.ff;
vis[curr.ss] = true;
for (pair <ll, int> p : Adj[curr.ss]) {
if (!vis[p.ss]) to.push({p.ff + curr.ff, p.ss}), V[p.ss].parent = curr.ss, V[p.ss].pdist = p.ff;
}
}
// Encuentra el más lejano
pair <ll, int> best = {-1, -1};
for (int i=0; i<sze; i++) {
// No pertence a esta componente
if (!vis[i]) {
excluded = i;
continue;
}
if (dist[i] != 0) best = max(best, {dist[i], i});
}
return best;
}
ll Diametro() {
// Devuelve el diametro
pair <ll, int> rx = DFS(0);
pair <ll, int> ry = DFS(rx.ss);
return ry.ff;
}
// Encuentra el radio. Devuele el centro
int Radio(int o = 0) {
//cerr << "--- PRIMERA DFS ---" << endl;
pair <ll, int> rx = DFS(o);
//cerr << "(" << rx.ff << ", " << rx.ss << ")" << endl;
//cerr << "El excluido es " << excluded << endl;
//cerr << "--- SEGUNDA DFS ---" << endl;
pair <ll, int> ry = DFS(rx.ss);
//cerr << "(" << ry.ff << ", " << ry.ss << ")" << endl;
int curr = ry.ss;
int best = curr;
ll a = ry.ff, b = 0;
ll maxi = INF;
//cerr << "--- BUSCANDO RADIO ---" << endl;
while (curr != rx.ss) {
//cerr << "Revisando " << curr << endl;
if (max(a,b) < maxi) best = curr, maxi = max(a,b);
a -= V[curr].pdist;
b += V[curr].pdist;
curr = V[curr].parent;
}
return best;
}
};
Graph G;
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
G = Graph(n);
//cerr << "Creando grafo... OK" << endl;
for (int i=0; i<m; i++) {
G.Adj[A[i]].pb({T[i], B[i]});
G.Adj[B[i]].pb({T[i], A[i]});
}
//cerr << "Llenando grafo... OK" << endl;
int g1 = G.Radio();
//cerr << "Primer centro " << g1 << endl;
int g2 = G.Radio(G.excluded);
//cerr << "Segundo centro " << g2 << endl;
G.Adj[g2].pb({(ll)(l), g1});
G.Adj[g1].pb({(ll)(l), g2});
return G.Diametro();
}
