#include <bits/stdc++.h>
#include "dreaming.h
using namespace std;
namespace Solve {
vector <pair <int, int>> adia[100010];
int g[100010];
bool viz[100010];
vector <int> dist;
int tata[100010];
int g_tata[100010];
int n, ans = 0;
int get_mij_diam(int nod) {
auto calc_d = [](int nod) {
tata[nod] = 0;
vector <pair <int, pair <int, int>>> v = { { 0, { nod, 0 } } };
pair <int, int> dmax = { 0, 0 };
while (!v.empty()) {
auto x = v.back();
v.pop_back();
viz[x.second.first] = 1;
dmax = max(dmax, { x.first, x.second.first });
for (auto i : adia[x.second.first]) {
if (i.first != x.second.second) {
tata[i.first] = x.second.first;
g_tata[i.first] = i.second;
v.push_back({ x.first + i.second, { i.first, x.second.first } });
}
}
}
return dmax;
};
nod = calc_d(nod).second;
auto d = calc_d(nod);
int best = 1e9;
ans = max(ans, d.first);
for (int i = d.second, l = d.first; i; l -= g_tata[i], i = tata[i])
best = min(best, max(l, d.first - l));
return best;
}
int solve(int l) {
for (int i = 1; i <= n; i++)
if (!viz[i])
dist.push_back(get_mij_diam(i));
sort(dist.rbegin(), dist.rend());
if (dist.size() == 1)
return ans;
if (dist.size() == 2)
return max(ans, l + dist[0] + dist[1]);
return max(ans, max(2 * l + dist[1] + dist[2], l + dist[0] + dist[1]));
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
Solve::n = N;
for (int i = 0; i < M; i++)
Solve::adia[A[i] + 1].push_back({ B[i] + 1, T[i] }), Solve::adia[B[i] + 1].push_back({ A[i] + 1, T[i] });
return Solve::solve(L);
}
/*
int A[] = { 0, 8, 2, 5, 5, 1, 1, 10 };
int B[] = { 8, 2, 7, 11, 1, 3, 9, 6 };
int T[] = { 4, 2, 4, 3, 7, 1, 5, 3 };
int main()
{
cout << travelTime(12, 8, 2, A, B, T);
return 0;
}
*/
Compilation message
dreaming.cpp:2:10: warning: missing terminating " character
#include "dreaming.h
^
dreaming.cpp:2:10: error: #include expects "FILENAME" or <FILENAME>
#include "dreaming.h
^~~~~~~~~~~
