#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 2;
int up[N], k, down[N], bestTime[N];
bool viz[N];
vector<pair<int, int> > G[N];
void dfs (int nod, int p) {
for (auto it : G[nod])
if (it.first != p) {
dfs(it.first, nod);
down[nod] = max(down[nod], down[it.first] + it.second);
}
}
void dfs2 (int nod, int p) {
vector<int>pref;
vector<int>suf;
viz[nod] = 1;
for (auto it : G[nod])
if (it.first != p) {
up[it.first] = up[nod] + it.second;
pref.push_back(down[it.first] + it.second);
}
suf = pref;
for (int i = 1; i < pref.size(); i++)
pref[i] = max(pref[i - 1], pref[i]);
for (int i = suf.size() - 2; i >= 0; i--)
suf[i] = max(suf[i + 1], suf[i]);
int useless = 0;
for (auto it : G[nod])
if (it.first != p) {
int value = 0;
if (useless > 0)
value = pref[useless - 1];
if (useless < suf.size() - 1)
value = max(value, suf[useless + 1]);
up[it.first] = max(up[it.first], value + it.second);
useless++;
dfs2(it.first, nod);
}
bestTime[k] = min(bestTime[k], max(down[nod], up[nod]));
}
int timeTravel (int n, int m, int l, int a[], int b[], int t[]) {
for (int i = 0; i < m; i++) {
G[a[i]].push_back({b[i], t[i]});
G[b[i]].push_back({a[i], t[i]});
}
for (int i = 1; i <= n; i++)
if (!viz[i]) {
k++;
bestTime[k] = 1e9 + 2;
dfs(i, 0);
dfs2(i, 0);
}
sort(bestTime + 1, bestTime + k + 1, greater<int>());
if (k == 1)
return bestTime[1];
if (k == 2)
return l + bestTime[1] + bestTime[2];
else
return max(l + bestTime[1] + bestTime[2], bestTime[2] + bestTime[3] + 2 * l);
}
int a[N], b[N], t[N], n, m, l;
/*int main ()
{
cin >> n >> m >> l;
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i] >> t[i];
a[i]++; b[i]++;
}
cout << timeTravel(n, m, l, a, b, t);
return 0;
}*/
/**
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
**/
Compilation message
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 1; i < pref.size(); i++)
| ~~^~~~~~~~~~~~~
dreaming.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (useless < suf.size() - 1)
| ~~~~~~~~^~~~~~~~~~~~~~~~
/tmp/ccnuAuTY.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
