#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <memory.h>
#include <assert.h>
using namespace std;
const int N_ = 200005;
const int C = 10005;
const int inf = 1987654321;
struct Edge {
int v, c;
Edge(): v(0), c(0) { }
Edge(int v, int c): v(v), c(c) { }
};
struct Root {
int v, c;
Root(): v(0), c(0) { }
Root(int v, int c): v(v), c(c) { }
bool operator< (const Root &t) const { return c < t.c; }
};
int N, M, L;
vector<Edge> Gph[N_];
int farch[N_][2], farthest[N_];
int Que[N_], Par[N_], Cst[N_], Qf, Qr;
bool visited[N_];
priority_queue<Root> H;
int res;
void findRoot (int r) {
Qf = Qr = 0; Que[++Qr] = r;
visited[r] = 1;
while(Qf < Qr) {
int u = Que[++Qf]; //printf("%d(%d) ", u, Par[u]);
for(int i = 0; i < Gph[u].size(); i++) {
Edge &e = Gph[u][i];
if(!visited[e.v]) {
visited[e.v] = 1;
Par[e.v] = u; Cst[e.v] = e.c;
Que[++Qr] = e.v;
}
}
}
//puts("");
for(int i = Qr; i > 0; i--) {
int u = Que[i], p = Par[u], c = Cst[u] + farch[u][0];
//printf("%d: %d %d\n", u, farch[u][0], farch[u][1]);
if(farch[p][0] < c) {
farch[p][1] = farch[p][0];
farch[p][0] = c;
}else if(farch[p][1] < c){
farch[p][1] = c;
}
}
Qf = Qr = 0; Que[++Qr] = r;
while(Qf < Qr) {
int u = Que[++Qf];
for(int i = 0; i < Gph[u].size(); i++) {
Edge &e = Gph[u][i];
if(Par[e.v] != u) continue;
Que[++Qr] = e.v;
int w = (e.c + farch[e.v][0] >= farch[u][0]);
farthest[e.v] = e.c + max(farthest[u], farch[u][w]);
}
}
int root = r;
for(int i = 1; i <= Qr; i++) {
int u = Que[i];
farthest[u] = max(farthest[u], farch[u][0]);
res = max(res, farthest[u]);
res = max(res, farch[u][0] + farch[u][1]);
if(farthest[u] < farthest[root]) root = u;
}
H.push(Root(root, farthest[root]));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int i, j;
::N = N; ::M = M; ::L = L;
for(i = 0; i < M; i++) {
int u = A[i]+1, v = B[i]+1;
Gph[u].push_back(Edge(v, T[i]));
Gph[v].push_back(Edge(u, T[i]));
}
for(i = 1; i <= N; i++) {
if(!visited[i]) findRoot(i);
}
while(H.size() > 1) {
Root r2 = H.top(); H.pop();
Root r1 = H.top(); H.pop();
res = max(res, r1.c + L + r2.c);
Gph[r1.v].push_back( Edge(r2.v, L) );
Gph[r2.v].push_back( Edge(r1.v, L) );
H.push( Root(r2.v, max(r1.c + L, r2.c)) );
}
memset(visited, 0, sizeof visited);
memset(farch, 0, sizeof farch);
memset(farthest, 0, sizeof farthest);
memset(Cst, 0, sizeof Cst);
findRoot(1);
return res;
}
