#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
/*
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;*/
#define INF 1000000000000000006
#define MAXN 100005
ll N, M, cen, mxdep, par[MAXN], ext1, ext2, depth[MAXN], K;
vll g[MAXN];
bool vis[MAXN];
void dfs1(int a, int dep)
{
if(mxdep < dep)
mxdep = dep, ext1 = a;
for(pll bb : g[a])
if(!vis[bb.ff])
vis[bb.ff] = true, dfs1(bb.ff, dep + bb.ss);
}
void dfs2(int a, int p, int dep)
{
// cerr<<a<<' ';
if(mxdep < dep)
mxdep = dep, ext2 = a;
par[a] = p;
depth[a] = dep;
for(pll bb : g[a])
if(bb.ff != p)
dfs2(bb.ff, a, bb.ss + dep);
}
void dfs3(int a)
{
if(a == -1)
return;
if(mxdep > max(depth[a], depth[ext2] - depth[a]))
mxdep = max(depth[a], depth[ext2] - depth[a]), cen = a;
dfs3(par[a]);
}
vi Lenghts;
int solve()
{
F0R(i, N)
vis[i] = false;
ll tt = 0;
F0R(i, N)
{
if(!vis[i])
{
// cerr<<"not cisited["<<i<<"]\n";
vis[i] = true;
mxdep = -1;
dfs1(i, 0);
mxdep = -1;
dfs2(ext1, -1, 0);
tt = max(tt, mxdep);
mxdep = INF;
dfs3(ext2);
Lenghts.pb(mxdep);
// cerr<<"\nmxdep = "<<mxdep<<", ext1 = "<<ext1<<", ext2 = "<<ext2<<'\n';
}
}
sort(all(Lenghts), greater<ll>());
ll ans;
if((int)Lenghts.size() == 1)
ans = Lenghts[0];
else if ((int)Lenghts.size() == 2)
ans = Lenghts[1] + Lenghts[0] + K;
else
ans = max(Lenghts[1] + K + Lenghts[0], Lenghts[1] + K + K + Lenghts[2]);
return max(tt, ans);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
N = n;
M = m;
K = L;
F0R(i, M)
g[A[i]].pb(mp(B[i], T[i])), g[B[i]].pb(mp(A[i], T[i]));
return solve();
}
signed main()
{
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
int n, m, L;
cin>>n>>m>>L;
int A[m], B[m], T[m];
F0R(i, m)
cin>>A[i]>>B[i]>>T[i];
cout<<travelTime(n, m, L, A, B, T)<<'\n';
return 0;
}
Compilation message
/tmp/ccclqNqv.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc0ZGEjx.o:grader.c:(.text.startup+0x0): first defined here
/tmp/cc0ZGEjx.o: In function `main':
grader.c:(.text.startup+0xa7): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
