#include "dreaming.h"
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pi;
inline vector<int> getTreeDiameters(const vector<vector<pi>>& g)
{
const int N = g.size();
vector<bool> visited(N, false);
const auto getFurthest = [&](const int start, vector<int>& dist) -> int
{
int result = start;
queue<int> q({start});
visited[start] = true;
while (! q.empty())
{
const int u = q.front();
q.pop();
for (const pi& p : g[u])
if (! visited[p.second])
{
q.push(p.second);
visited[p.second] = true;
dist[p.second] = dist[u] + p.first;
// cout << u << " -> " << p.second << ", dist " << dist[u] << " -> " << dist[p.second] << endl;
if (dist[result] < dist[p.second])
result = p.second;
}
}
return result;
};
const auto getMinDist = [&](const int start, const vector<int>& du, const vector<int>& dv) -> int
{
int result = max(du[start], dv[start]);
queue<int> q({start});
visited[start] = true;
while (! q.empty())
{
const int u = q.front();
q.pop();
for (const pi& p : g[u])
if (! visited[p.second])
{
q.push(p.second);
visited[p.second] = true;
result = min(result, max(du[p.second], dv[p.second]));
}
}
return result;
};
vector<int> tree_u, tree_v, d_(N, 0), du(N, 0), dv(N, 0);
for (int i = 0; i < N; i ++)
if (! visited[i])
tree_u.push_back(getFurthest(i, d_));
// cout << "then for u, \n";
visited = vector<bool>(N, 0);
for (const int& u : tree_u)
tree_v.push_back(getFurthest(u, du));
if (tree_u.size() == 1) return {*max(du.begin(), du.end())};
// cout << "then for v, \n";
visited = vector<bool>(N, 0);
for (const int& v : tree_v)
getFurthest(v, dv);
vector<int> result;
visited = vector<bool>(N, 0);
for (const int& u : tree_u)
result.push_back(getMinDist(u, du, dv));
sort(result.rbegin(), result.rend());
return result;
}
inline int getArrangedTime(const vector<int>& tree, const int& L)
{
cout << "tree: ";
for (const int& p : tree) cout << p << " ";
cout << endl;
if (tree.size() == 1) return tree[0];
int u = 0, v = 1, N = tree.size(), p[N], left = 100000, right = 100002;
p[0] = 100001;
p[1] = 100002;
const auto distance = [&](const int& a, const int& b, const int& pa, const int& pb) -> int { return tree[a] + tree[b] + L * abs(pa - pb); };
int cur = distance(u, v, p[u], p[v]);
for (int i = 2; i < tree.size(); i ++)
{
const int left_dist = max(distance(u, i, p[u], left), distance(v, i, p[v], left)),
right_dist = max(distance(u, i, p[u], right), distance(v, i, p[v], right));
if (left_dist < right_dist)
{
p[i] = left --;
cur = max(cur, left_dist);
}
else
{
p[i] = right ++;
cur = max(cur, right_dist);
}
}
return cur;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
vector<vector<pi>> g(N);
for (int i = 0; i < M; i ++)
{
g[A[i]].push_back(make_pair(T[i], B[i]));
g[B[i]].push_back(make_pair(T[i], A[i]));
}
return getArrangedTime(getTreeDiameters(g), L);
}
// int main()
// {
// int N = 12, M = 8, L = 2,
// A[8] = {0,8,2,5,5,1,1,10},
// B[8] = {8,2,7,11,1,3,9,6},
// C[8] = {4,2,4,3,7,1,5,3};
// cout << travelTime(N, M, L, A, B, C);
// return 0;
// }
