#include "dreaming.h"
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cstdlib>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> II;
typedef long long llong;
const int INF = 2e9;
struct Edge {
int to, len;
};
typedef vector< vector<Edge> > Graph;
Graph extract_graph(int N, int M, int A[], int B[], int T[]) {
Graph adj(N);
for (int j = 0; j < M; ++j) {
int u = A[j], v = B[j], len = T[j];
adj[u].push_back({v, len});
adj[v].push_back({u, len});
}
return adj;
}
void dfs1(const Graph& G, vector<bool>& vis, VI& comp, int u) {
vis[u] = true;
comp.push_back(u);
for (Edge e : G[u]) {
if (vis[e.to]) continue;
dfs1(G, vis, comp, e.to);
}
}
Graph renumerate(const Graph& G, const VI& comp) {
map<int,int> new_id;
for (int u : comp) {
int id = new_id.size();
new_id[u] = id;
}
Graph new_graph(comp.size());
for (int u : comp) {
int uid = new_id[u];
for (Edge e : G[u]) {
assert( new_id.count(e.to) );
int vid = new_id[e.to];
new_graph[uid].push_back({vid, e.len});
}
}
return new_graph;
}
void dfs2(const Graph& tree, VI& D, int u, int d = 0) {
D[u] = d;
for (Edge e : tree[u]) {
if (D[e.to] >= 0) continue;
dfs2(tree, D, e.to, d+e.len);
}
}
II get_center_distances(const Graph& tree) {
const int N = tree.size();
if (N == 1)
return {0, 0};
VI D(N, -1);
dfs2(tree, D, 0);
int u_max = 0;
for (int u = 0; u < N; ++u) {
if (D[u] > D[u_max])
u_max = u;
}
VI D1(N, -1);
dfs2(tree, D1, u_max);
int v_max = 0;
for (int v = 0; v < N; ++v) {
if (D1[v] > D1[v_max])
v_max = v;
}
VI D2(N, -1);
dfs2(tree, D2, v_max);
II best(INF, INF);
for (int u = 0; u < N; ++u) {
II cur(D1[u], D2[u]);
if (cur.first < cur.second)
swap(cur.first, cur.second);
best = min(best, cur);
}
return best;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector< vector<Edge> > G = extract_graph(N, M, A, B, T);
vector<Graph> trees;
vector<bool> vis(N, false);
for (int u = 0; u < N; ++u) {
if (!vis[u]) {
VI comp;
dfs1(G, vis, comp, u);
Graph C = renumerate(G, comp);
trees.emplace_back(C);
}
}
vector<II> center_distances;
for (Graph t : trees) {
II cd = get_center_distances(t);
center_distances.push_back(cd);
// cerr << cd.first << ',' << cd.second << endl;
}
sort(center_distances.begin(), center_distances.end(), greater<II>());
int res = 0;
for (II cd : center_distances)
res = max(res, cd.first + cd.second);
if (int(center_distances.size()) > 1) {
res = max(res,
center_distances[0].first + L + center_distances[1].first);
for (int j = 2; j < int(center_distances.size()); ++j) {
res = max(res,
center_distances[j].first + 2*L + center_distances[1].first);
}
}
return res;
}
