#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int n, m, DFSTime, CC;
int imax[4][N], belong[N], cntCC;
ll res, R[N], l, dist[4][N], maxdist;
vector<pii> adj[N];
void DFS(int u, int p)
{
for (pii e : adj[u]) {
int v = e.fi, w = e.se;
if (DFSTime == 0) belong[v] = CC;
if (v == p) continue;
dist[DFSTime][v] = dist[DFSTime][u] + w;
if (dist[DFSTime][v] > maxdist) {
maxdist = dist[DFSTime][v];
imax[DFSTime][cntCC] = v;
}
DFS(v, u);
}
}
void solve()
{
sort(R + 1, R + CC + 1, greater<ll>());
// 1 bridge
if (CC >= 2) res = max(res, R[1] + R[2] + l);
// 2 bridge
if (CC >= 3) res = max(res, R[2] + R[3] + l * 2);
cout << res << '\n';
}
int main()
{
#ifdef NDT
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> l;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 0; i < n; ++i) {
if (dist[DFSTime][i]) continue;
cntCC = ++CC;
imax[DFSTime][cntCC] = i;
belong[i] = CC;
maxdist = 0;
DFS(i, i);
}
++DFSTime;
for (int i = 1; i <= CC; ++i) {
maxdist = 0;
cntCC = i;
imax[DFSTime][cntCC] = i;
DFS(imax[DFSTime - 1][i], imax[DFSTime - 1][i]);
res = max(res, maxdist);
}
++DFSTime;
for (int i = 1; i <= CC; ++i) {
maxdist = 0;
cntCC = i;
imax[DFSTime][cntCC] = i;
DFS(imax[DFSTime - 1][i], imax[DFSTime - 1][i]);
}
for (int i = 1; i <= CC; ++i) R[i] = 1e15;
for (int i = 0; i < n; ++i) {
R[belong[i]] = min(R[belong[i]], max(dist[1][i], dist[2][i]));
}
solve();
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cclhBNQl.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNRiA0m.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccNRiA0m.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
