#include "dreaming.h" #include <algorithm> #include <iostream> #include <queue> #include <utility> #include <vector> using namespace std; void getMaxDist(int cur, int par, vector<vector<pair<int, int> > > &adjacency, vector<int> &maxDist, vector<bool> &visited) { visited[cur] = true; for (auto &[nxt, len] : adjacency[cur]) { if (nxt == par) continue; getMaxDist(nxt, cur, adjacency, maxDist, visited); maxDist[cur] = max(maxDist[cur], maxDist[nxt] + len); } } int minDist(int cur, int par, int parMaxDist, vector<vector<pair<int, int> > > &adjacency, vector<int> &maxDist) { vector<pair<int, pair<int, int> > > dists; dists.push_back(make_pair(0, make_pair(-1, -1))); for (auto &[nxt, len] : adjacency[cur]) { if (nxt == par) dists.push_back(make_pair(parMaxDist, make_pair(par, len))); else dists.push_back(make_pair(maxDist[nxt] + len, make_pair(nxt, len))); } sort(dists.rbegin(), dists.rend()); if (dists.size() == 1) return 0; if (dists[1].first + dists[0].second.second < dists[0].first) { return minDist(dists[0].second.first, cur, dists[1].first + dists[0].second.second, adjacency, maxDist); } return dists[0].first; } int maxDistWithIn(int cur, int par, vector<vector<pair<int, int> > > &adjacency, vector<int> &maxDist) { vector<int> dists(2, 0); int maxRes = 0; for (auto &[nxt, len] : adjacency[cur]) { if (nxt == par) continue; maxRes = max(maxRes, maxDistWithIn(nxt, cur, adjacency, maxDist)); dists.push_back(maxDist[nxt] + len); } sort(dists.rbegin(), dists.rend()); return max(maxRes, dists[0] + dists[1]); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { vector<vector<pair<int, int> > > adjacency(N); for (int i = 0; i < M; ++i) { adjacency[A[i]].emplace_back(B[i], T[i]); adjacency[B[i]].emplace_back(A[i], T[i]); } vector<int> maxDist(N); vector<int> components; vector<bool> visited(N, false); int maxRes = 0; for (int i = 0; i < N; ++i) { if (visited[i]) continue; getMaxDist(i, -1, adjacency, maxDist, visited); components.push_back(minDist(i, -1, -1, adjacency, maxDist)); maxRes = max(maxRes, maxDistWithIn(i, -1, adjacency, maxDist)); } sort(components.rbegin(), components.rend()); if (components.size() == 1) return max(components[0], maxRes); else if (components.size() == 2) return max(components[0] + components[1] + L, maxRes); else return max(components[1] + max(components[0] + L, components[2] + 2 * L), maxRes); }