#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef long long int ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
#define prt(x) #x << ": " << x
#define sz(x) (int)(x).size()
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
#define pb push_back
#define vt vector
#define s second
#define f first
template <class A, class B> ostream &operator<<(ostream &out, const pair<A, B> &a){
return out << "(" << a.f << ", " << a.s << ")";
}
template <class A> ostream &operator<<(ostream &out, const vector<A> &v){
out << "[";
for (int i = 0; i < sz(v); ++i) {
if (i)
out << ", ";
out << v[i];
}
return out << "]";
}
template <int MOD> struct ModInt{
unsigned x;
ModInt() : x(0) { }
ModInt(signed sig) : x(sig) { }
ModInt(signed long long sig) : x(sig%MOD) { }
int get() const { return (int)x; }
ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
bool operator<(ModInt that) const { return x < that.x; }
friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};
typedef ModInt<1000000007> mint;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f, mxn = 1e5 + 5;
bool vis[mxn];
vt<pii> g[mxn];
int parent[mxn], v1, v2, ans, dp[mxn];
void dfs1(int v, int p, int depth){
vis[v] = true;
if(depth > ans){
ans = depth;
v1 = v;
}
for(auto i : g[v]){
if(i.f == p){
continue;
}
dfs1(i.f, v, depth + i.s);
}
}
void dfs2(int v, int p, int depth){
parent[v] = p;
dp[v] = depth;
if(depth > ans){
ans = depth;
v2 = v;
}
for(auto i : g[v]){
if(i.f == p){
continue;
}
dfs2(i.f, v, depth + i.s);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, l;
cin >> n >> m >> l;
for(int i = 0; i < m; ++i){
int u, v, w;
cin >> u >> v >> w;
++u;
++v;
g[u].pb({ v, w });
g[v].pb({ u, w });
}
int answer;
vt<int> r;
for(int i = 1; i <= n; ++i){
if(!vis[i]){
v1 = v2 = i;
ans = 0;
dfs1(i, i, 0);
ans = 0;
dfs2(v1, v1, 0);
answer = ans;
while(v2 != v1){
answer = min(answer, max(dp[v2], ans - dp[v2]));
v2 = parent[v2];
}
r.pb(answer);
}
}
sort(r.rbegin(), r.rend());
answer = r[0];
if(sz(r) > 1){
answer = max(answer, r[0] + r[1] + l);
}
if(sz(r) > 2){
answer = max(answer, r[1] + r[2] + 2 * l);
}
cout << answer;
}
Compilation message
/usr/bin/ld: /tmp/ccIpyM2d.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cciGe1dd.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cciGe1dd.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
