// code by wapas
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solution(int t) {
int N, M, L; cin >> N >> M >> L;
vector<vector<pair<ll, ll>>> adjList(N);
for (int i = 0; i < M; i++) {
int a, b, w; cin >> a >> b >> w;
adjList[a].push_back({ b, w });
adjList[b].push_back({ a, w });
}
vector<bool> chk(N);
ll res = 0, resMax = 0, s = 0, e = 0;
function<void (ll, ll, ll)> dfs = [&](ll curr, ll prev, ll sum) {
chk[curr] = true;
if (resMax < sum) {
res = curr;
resMax = sum;
}
for (auto [next, weight] : adjList[curr]) if (next != prev) dfs(next, curr, sum + weight);
};
ll res2 = 0;
function<bool (ll, ll, ll)> dfs2 = [&](ll curr, ll prev, ll sum) {
bool flag = false;
for (auto [next, weight] : adjList[curr]) {
if (next != prev) {
if (dfs2(next, curr, sum + weight)) {
flag = true;
res2 = min(res2, max(resMax - sum, sum));
}
}
}
return flag || curr == e;
};
ll ans = 0;
auto getTreeRadius = [&](int node) {
res = 0; resMax = -1;
dfs(node, -1, 0);
resMax = -1;
s = res;
dfs(res, -1, 0);
e = res;
ans = max(ans, resMax);
res2 = 1e18;
dfs2(s, -1, 0);
if (res2 == 1e18) res2 = 0;
return res2;
};
vector<ll> cadi;
for (int i = 0; i < N; i++) {
if (chk[i]) continue;
cadi.push_back(getTreeRadius(i));
}
sort(cadi.begin(), cadi.end());
reverse(cadi.begin(), cadi.end());
if (cadi.size() > 2) ans = max(ans, cadi[0] + cadi[1] + L);
if (cadi.size() > 3) ans = max(ans, cadi[1] + cadi[2] + L + L);
cout << ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// int T; cin >> T;
int T = 1;
for (int t = 0; t < T; t++) {
solution(t);
}
}
Compilation message
/usr/bin/ld: /tmp/ccF0Mwtd.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cclAtJLe.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cclAtJLe.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
