#include<bits/stdc++.h>
//#include "dreaming.h"
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
const int inf = 1e9, N = 1e6;
int travelTime2(int n, int l, vector<int> s) {
//cout << n << '\n';
//for (int x: s) cout << x << ' ';
//cout << '\n';
if (n == 1) return 0;
if (sz(s) == 1 && n == 3) return s[0] + l;
if (sz(s) == 2 && n == 4) return s[0] + s[1] + l;
if (n == 2) {
if (sz(s)) return s[0];
return l;
}
s.push_back(0);
s.push_back(0);
s.push_back(0);
sort(rall(s));
return max(s[0] + s[1] + l, s[1] + s[2] + 2 * l);
}
vector<int> d0(N, inf), d1(N, inf);
vector<pii> g[N];
int val;
int calc(int x, int n) {
set<pii> s;
vector<int> h;
d0[x] = 0;
s.insert({0, x});
int a = x;
while (sz(s)) {
x = (*s.begin()).s;
if (d0[x] > d0[a]) a = x;
h.push_back(x);
s.erase(s.begin());
for (auto [to, w]: g[x]) {
if (d0[to] <= d0[x] + w) continue;
s.erase({d0[to], to});
d0[to] = d0[x] + w;
s.insert({d0[to], to});
}
}
d1[a] = 0;
s.insert({0, a});
int b = a;
while (sz(s)) {
x = (*s.begin()).s;
if (d1[x] > d1[b]) b = x;
s.erase(s.begin());
for (auto [to, w]: g[x]) {
if (d1[to] <= d1[x] + w) continue;
s.erase({d1[to], to});
d1[to] = d1[x] + w;
s.insert({d1[to], to});
}
}
val = max(val, d1[b]);
for (int v: h) d0[v] = inf;
d0[b] = 0;
s.insert({0, b});
while (sz(s)) {
x = (*s.begin()).s;
s.erase(s.begin());
for (auto [to, w]: g[x]) {
if (d0[to] <= d0[x] + w) continue;
s.erase({d0[to], to});
d0[to] = d0[x] + w;
s.insert({d0[to], to});
}
}
int ans = inf;
for (int v: h) {
x = max(d0[v], d1[v]);
ans = min(ans, x);
d0[v] = d1[v] = inf;
}
return ans;
}
int p[N], sz[N];
int get(int x) {
if (p[x] == x) return x;
return p[x] = get(p[x]);
}
void unite(int a, int b) {
a = get(a), b = get(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
p[a] = b;
sz[b] += sz[a];
}
int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
for (int i = 0; i < n; i++) p[i] = i, sz[i] = 1;
for (int i = 0; i < m; i++) {
g[a[i]].push_back({b[i], c[i]});
g[b[i]].push_back({a[i], c[i]});
unite(a[i], b[i]);
}
vector<int> s;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == get(i)) cnt++;
if (i == get(i) && sz[i] > 1) s.push_back(calc(i, n)), cnt++;
}
return max(val, travelTime2(cnt, l, s));
}
#ifdef M
main() {
//freopen("rsq.in", "r", stdin);
//freopen("rsq.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, l;
cin >> n >> m >> l;
int a[m], b[m], c[m];
for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i];
cout << travelTime(n, m, l, a, b, c);
}
#endif
Compilation message
/usr/bin/ld: /tmp/ccvxuwFD.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
