#include<bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<int> vi;
const ll maxn=2e5+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
vector<int> adj[maxn];
bool vis[maxn];
int a[maxn],b[maxn],t[maxn],dep[maxn];
int dfs(int u,int pre)
{
int x=u,y;
vis[u]=true;
for(int i: adj[u])
{
int v=u^a[i]^b[i];
int w=t[i];
if (v==pre) continue;
dep[v]=dep[u]+w;
y=dfs(v,u);
if (dep[y]>dep[x]) x=y;
}
return x;
}
vector<int> L;
bool ok=0;
void dfs1(int u,int pre,int aim)
{
L.pb(u);
if (u==aim) ok=1;
if (ok) return;
for(int i: adj[u])
{
int v=u^a[i]^b[i];
int w=t[i];
if (v==pre) continue;
dfs1(v,u,aim);
if (ok) return;
}
L.pop_back();
}
int Find_diameter(int u)
{
dep[u]=0;
u=dfs(u,u);
dep[u]=0;
int v=dfs(u,u);
// cerr<< "wtf "<<v<<'\n';
ok=0;
L.clear();
dfs1(u,u,v);
// for(int kz:L) cerr<< "ad "<<kz<<' '<<dep[kz]<<' '<<dep[v]-dep[kz]<<'\n';
for1(i,0,L.size()-2)
{
// cerr<< "clmm "<<L[i]<<'\n';
int x1=max(dep[L[i]],dep[v]-dep[L[i]]);
int x2=max(dep[L[i+1]],dep[v]-dep[L[i+1]]);
if (x2>=x1) return x1;
}
}
vector<int> Lis;
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
for1(i,1,m)
{
a[i]=A[i-1]+1;
b[i]=B[i-1]+1;
t[i]=T[i-1];
}
for1(i,1,m)
{
adj[a[i]].pb(i);
adj[b[i]].pb(i);
// cerr<< a[i]<<' '<<b[i]<<' '<<t[i]<<'\n';
}
// return 2;
for1(i,1,n)
{
if (!vis[i])
{
int x=Find_diameter(i);
// cerr<< i<<' '<<x<<'\n';
Lis.pb(x);
}
}
// for(int v:Lis) cerr<< v<<'\n';
sort(all(Lis),greater<int>());
if (Lis.size()==1)
{
return Lis[0];
}
else
{
return Lis[0]+Lis[1]+l;
}
//return 42;
}
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int32_t main() {
int N, M, L, i;
int res;
FILE *f = fopen("dreaming.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
fclose(f);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
/*
3 5 2 4 1
*/
Compilation message
dreaming.cpp: In function 'void dfs1(long long int, long long int, long long int)':
dreaming.cpp:58:13: warning: unused variable 'w' [-Wunused-variable]
58 | int w=t[i];
| ^
dreaming.cpp: In function 'long long int Find_diameter(long long int)':
dreaming.cpp:9:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define for1(i,j,k) for(int i=(j);i<=(k);i++)
| ^
dreaming.cpp:76:5: note: in expansion of macro 'for1'
76 | for1(i,0,L.size()-2)
| ^~~~
dreaming.cpp: In function 'int32_t main()':
dreaming.cpp:148:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
148 | res = fscanf(f, "%d%d%d", &N, &M, &L);
| ~^ ~~
| | |
| int* long long int*
| %lld
dreaming.cpp:148:22: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
148 | res = fscanf(f, "%d%d%d", &N, &M, &L);
| ~^ ~~
| | |
| int* long long int*
| %lld
dreaming.cpp:148:24: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
148 | res = fscanf(f, "%d%d%d", &N, &M, &L);
| ~^ ~~
| | |
| int* long long int*
| %lld
dreaming.cpp:150:21: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
150 | res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
| ~^ ~~~~~
| | |
| int* long long int*
| %lld
dreaming.cpp:150:23: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
150 | res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
| ~^ ~~~~~
| | |
| int* long long int*
| %lld
dreaming.cpp:150:25: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
150 | res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
| ~^ ~~~~~
| | |
| int* long long int*
| %lld
dreaming.cpp:154:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
154 | printf("%d\n", answer);
| ~^ ~~~~~~
| | |
| int long long int
| %lld
dreaming.cpp:142:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
142 | int res;
| ^~~
dreaming.cpp: In function 'long long int Find_diameter(long long int)':
dreaming.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
83 | }
| ^
/usr/bin/ld: /tmp/cczv0bVq.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccZCgepq.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccZCgepq.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
