// SOLVED SUBTASK 1 (14 pts)
// SOLVED SUBTASK 2 (10 pts)
// SOLVED SUBTASK 3 (23 pts)
// UNSOLVED SUBTASK 4 (18 pts)
// UNSOLVED SUBTASK 5 (12 pts)
// UNSOLVED SUBTASK 6 (23 pts)
// [+-+]----------------------
// TOTAL 47/100 pts
#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
struct Edge {
int from;
int to;
int length;
Edge(int from, int to, int length) : from(from), to(to), length(length) {}
bool operator<(const Edge& other) {
return from < other.from;
}
};
bool operator<(const Edge& a, const Edge& b) {
return a.from < b.from;
}
int farthest_node(const std::vector<std::vector<Edge>>& tree, int a) {
std::vector<bool> visited(tree.size());
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
q.emplace(0, a);
int last;
while (!q.empty()) {
auto el = q.top();
q.pop();
if (visited[el.second]) continue;
visited[el.second] = true;
for (auto edge : tree[el.second]) {
q.emplace(el.first + edge.length, edge.to);
}
last = el.second;
}
return last;
}
std::vector<Edge> dijkstra_path(const std::vector<std::vector<Edge>>& tree, int a, int b) {
std::vector<bool> visited(tree.size());
std::priority_queue<std::pair<int, std::pair<Edge, int>>> q;
Edge dummy = Edge(-1, a, -1);
q.emplace(0, std::pair<Edge, int>(dummy, a));
std::vector<Edge> from(tree.size(), dummy);
while (!q.empty() && q.top().second.second != b) {
auto el = q.top();
q.pop();
if (visited[el.second.second]) continue;
visited[el.second.second] = true;
from[el.second.second] = el.second.first;
for (auto edge : tree[el.second.second]) {
q.emplace(el.first + edge.length, std::pair<Edge, int>(edge, edge.to));
}
}
if (q.empty()) return {};
from[b] = q.top().second.first;
std::vector<Edge> path;
int current = b;
while (current != a) {
path.push_back(from[current]);
current = from[current].from;
}
return path;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
std::vector<std::vector<Edge>> tree(N);
for (int i = 0; i < M; ++i) {
tree[A[i]].emplace_back(A[i], B[i], T[i]);
tree[B[i]].emplace_back(B[i], A[i], T[i]);
}
// std::cout << "finished init" << std::endl;
// floodfill
std::vector<int> color(N);
std::vector<int> parents;
int current = 1;
for (int i = 0; i < N; ++i) {
if (color[i]) continue;
parents.push_back(i);
std::vector<int> stack;
stack.push_back(i);
while (!stack.empty()) {
int back = stack.back();
stack.pop_back();
if (color[back]) continue;
color[back] = current;
for (auto edge : tree[back]) {
stack.push_back(edge.to);
}
}
++current;
}
// std::cout << "finished floodfill" << std::endl;
// radius and centers
std::vector<std::pair<int, int>> radius_centers(parents.size());
int sp = 0;
int largest_diameter = 0;
for (auto parent : parents) {
int b = farthest_node(tree, parent);
int a = farthest_node(tree, b);
if (a == b) {
radius_centers[sp++] = std::make_pair(0, parent);
continue;
}
auto diameter = dijkstra_path(tree, b, a);
int sum = 0;
for (auto edge : diameter) {
sum += edge.length;
}
largest_diameter = std::max(largest_diameter, sum);
int small_sum = 0;
int i = 0;
while (i < diameter.size() && small_sum <= sum / 2) {
small_sum += diameter[i++].length;
}
if (sum - small_sum + diameter[i - 1].length < small_sum) {
--i;
small_sum = sum - small_sum + diameter[i].length;
}
radius_centers[sp++] = std::make_pair(small_sum, i > 0 ? diameter[i - 1].from : diameter[i].to);
// if (sp % 100 == 0) {
// std::cout << "finished " << sp << " rads" << std::endl;
// }
}
// std::cout << "finished rads" << std::endl;
if (radius_centers.size() < 2) {
return largest_diameter;
}
std::sort(radius_centers.rbegin(), radius_centers.rend());
// std::cout << "finished sorting" << std::endl;
long long max = std::max(largest_diameter, radius_centers[0].first + L + radius_centers[1].first);
if (radius_centers.size() > 2) {
max = std::max(max, (long long)L + L + radius_centers[1].first + radius_centers[2].first);
}
return max;
}
