#include "dreaming.h"
#include <bits/stdc++.h>
#define MAX 100001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
vector<vector<pii>> g;
vector<int> used;
vector<int> e;
vector<int> dist;
vector<int> pre;
void dfs(int v,int prev){
e.pb(v);
used[v]=1;
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
dist[x.ff]=dist[v]+x.ss;
dfs(x.ff,v);
}
}
void dfs1(int v,int prev){
pre[v]=prev;
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
dist[x.ff]=dist[v]+x.ss;
dfs1(x.ff,v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int res;
g.resize(N);
dist.resize(N,0);
used.resize(N,0);
pre.resize(N,0);
for(int i=0;i<M;i++){
g[A[i]].pb(mp(B[i],T[i]));
g[B[i]].pb(mp(A[i],T[i]));
}
int maxd=0;
vector<int> c;
for(int i=0;i<N;i++){
if(used[i]==0){
e.clear();
dfs(i,-1);
int maxd1,ind;
maxd1=-1;
for(auto x:e){
if(dist[x]>maxd1){
maxd1=dist[x];
ind=x;
}
dist[x]=0;
}
dfs1(ind,-1);
maxd1=-1;
int ind1;
for(auto x:e){
if(dist[x]>maxd1){
maxd1=dist[x];
ind1=x;
}
}
maxd=max(maxd,maxd1);
int ind2=ind1;
int h=dist[ind1]-dist[ind];
while(ind1!=ind){
h=min(h,max(dist[ind2]-dist[ind1],dist[ind1]-dist[ind]));
ind1=pre[ind1];
}
c.pb(h);
}
}
sortv(c);
reverse(all(c));
if(c.size()==1){
res=c[0];
}
else{
res=c[0]+c[1]+L;
}
if(c.size()>2){
res=max(res,c[1]+c[2]+2*L);
}
res=max(maxd,res);
return res;
}
int main(){
int n,m,k;
cin >> n >> m >> k;
int A[m],B[m],T[m];
for(int i=0;i<m;i++){
cin >> A[i] >> B[i] >> T[i];
}
cout << travelTime(n,m,k,A,B,T);
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:121:19: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
121 | int h=dist[ind1]-dist[ind];
| ^
dreaming.cpp:122:14: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
122 | while(ind1!=ind){
| ~~~~^~~~~
/usr/bin/ld: /tmp/ccieYazq.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccR90v1o.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
