#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
vector <int> listVertex;
vector <vector <pair <int, int>>> adj;
vector <bool> visited;
vector <int> f_out, f_in;
vector <vector <int>> prefix, suffix;
void dfs_out(int u, int father) {
listVertex.push_back(u);
vector <pair <int, int>> children;
visited[u] = true;
for (int i = 0; i < (int) adj[u].size(); i++) {
pair <int, int> neighbor = adj[u][i];
if (neighbor.first != father) {
children.push_back(neighbor);
}
}
for (int i = 0; i < (int) children.size(); i++) {
dfs_out(children[i].first, u);
f_out[u] = max(f_out[u], f_out[children[i].first] + children[i].second);
}
prefix[u].clear();
prefix[u].resize((int) children.size() + 2);
prefix[u][0] = 0;
for (int i = 1; i <= (int) children.size(); i++) {
prefix[u][i] = max(prefix[u][i - 1], f_out[children[i - 1].first] + children[i - 1].second);
}
suffix[u].clear();
suffix[u].resize((int) children.size() + 2);
suffix[u][(int) children.size() + 1] = 0;
for (int i = (int) children.size(); i >= 1; i--) {
suffix[u][i] = max(suffix[u][i + 1], f_out[children[i - 1].first] + children[i - 1].second);
}
}
void dfs_in(int u, int father) {
vector <pair <int, int>> children;
for (int i = 0; i < (int) adj[u].size(); i++) {
pair <int, int> neighbor = adj[u][i];
if (neighbor.first == father) {
continue;
}
children.push_back(neighbor);
}
for (int i = 0; i < (int) children.size(); i++) {
pair <int, int> neighbor = children[i];
f_in[neighbor.first] = max(f_in[neighbor.first], f_in[u] + neighbor.second);
f_in[neighbor.first] = max(f_in[neighbor.first], max(prefix[u][i], suffix[u][i + 2]) + neighbor.second);
dfs_in(neighbor.first, u);
}
}
pair <int, int> solve(int u) {
listVertex.clear();
int n = (int) adj.size();
dfs_out(u, -1);
dfs_in(u, -1);
int minDist = 1000000007;
int ret;
for (int i = 0; i < (int) listVertex.size(); i++) {
int u = listVertex[i];
if (minDist > max(f_out[u], f_in[u])) {
minDist = max(f_out[u], f_in[u]);
ret = u;
}
}
return make_pair(minDist, ret);
}
int travelTime(int n, int m, int l, vector <int> a, vector <int> b, vector <int> t) {
adj.resize(n);
visited.resize(n, false);
for (int i = 0; i < m; i++) {
adj[a[i]].push_back(make_pair(b[i], t[i]));
adj[b[i]].push_back(make_pair(a[i], t[i]));
}
int ans = 0;
f_out.resize(n, 0);
f_in.resize(n, 0);
prefix.resize(n);
suffix.resize(n);
vector <pair <int, int>> save;
for (int i = 0; i < n; i++) {
if (visited[i] == false) {
save.push_back(solve(i));
}
}
sort(save.begin(), save.end());
reverse(save.begin(), save.end());
/*int minDist = 1000000007;
if ((int) save.size() >= 2) {
for (int i = 0; i < (int) save.size(); i++) {
int tmp;
if (i != (int) save.size() - 1) {
tmp = save[i].first + l + save.back().first;
}
else {
tmp = save[i].first + l + save[(int) save.size() - 2].first;
}
if ((int) save.size() > 2) {
int large1 = -1, large2 = -1;
for (int j = (int) save.size() - 1; j >= 0; j--) {
if (i != j) {
if (large1 == -1) {
large1 = j;
}
else if (large2 == -1) {
large2 = j;
}
else {
break;
}
}
}
tmp = max(tmp, 2 * l + save[large1].first + save[large2].first);
}
minDist = min(minDist, tmp);
}
} */
for (int u = 0; u < n; u++) {
ans = max(ans, max(f_out[u], f_in[u]));
}
if ((int) save.size() == 2) {
ans = max(ans, save[0].first + save[1].first + l);
}
if ((int) save.size() > 2) {
ans = max(ans, 2 * l + save[1].first + save[2].first);
}
return ans;
}
/*int main() {
cout << travelTime(12, 8, 2, {0, 8, 2, 5, 5, 1, 1, 10}, {8, 2, 7, 11, 1, 3, 9, 6}, {4, 2, 4, 3, 7, 1, 5, 3});
system("pause");
return 0;
} */
