#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector <pair <int, int>> adj[N];
int par[N], dis[N];
queue <int> que;
void BFS(int u, int &diam, int &dist) {
int far = u; diam = 0;
que.push(u); dis[u] = 0; par[u] = -1;
while (que.size()) {
u = que.front(); que.pop();
if (dis[u] > diam) {
diam = dis[u]; far = u;
}
for (auto e : adj[u]) {
int v, w; tie(v, w) = e;
if (v != par[u]) {
dis[v] = dis[u] + w;
par[v] = u; que.push(v);
}
}
}
que.push(u = far);
diam = dis[u] = 0; par[u] = -1;
while (que.size()) {
u = que.front(); que.pop();
if (dis[u] > diam) {
diam = dis[u]; far = u;
}
for (auto e : adj[u]) {
int v, w; tie(v, w) = e;
if (v != par[u]) {
dis[v] = dis[u] + w;
par[v] = u; que.push(v);
}
}
}
dist = INT_MAX; u = far;
while (u >= 0) {
dist = min(dist, max
(dis[u], dis[far] - dis[u]));
u = par[u];
}
}
int travelTime(int n, int m, int l,
vector <int> a, vector <int> b, vector <int> t) {
for (int i = 0; i < m; i++) {
adj[a[i]].emplace_back(b[i], t[i]);
adj[b[i]].emplace_back(a[i], t[i]);
}
memset(dis, -1, sizeof dis);
vector <int> tmp; int res = 0;
for (int i = 0; i < n; i++)
if (dis[i] < 0) {
int diam, dist;
BFS(i, diam, dist);
res = max(res, diam);
tmp.push_back(dist);
}
sort(tmp.begin(), tmp.end());
for (int i = 0; i + 1 < n - m; i++)
tmp[i] += l;
sort(tmp.begin(), tmp.end());
if (n - m > 1)
res = max(res,
tmp[n - m - 1] + tmp[n - m - 2]);
return res;
}
Compilation message
/tmp/ccHbreNo.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
