#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int N,M,L;
int Y[100010],tl,inl;
int tmp[100010],Q[100010][3];
int check[100010];
struct line{
line(){}
line(int en,int len):en(en),len(len){}
int en,len;
};
vector <line> edge[100010];
int far(int x)
{
int fr=1,re=0,ret=x,mx=0;
Q[0][0]=x;Q[0][1]=0;check[x]=1;
while(fr!=re){
int i;
for(i=0;i<edge[Q[re][0]].size();i++){
int tx=edge[Q[re][0]][i].en;
if(check[tx])continue;
check[tx]=1;
Q[fr][0]=tx;
Q[fr][1]=Q[re][1]+edge[Q[re][0]][i].len;
if(mx<Q[fr][1]){
mx=Q[fr][1];
ret=Q[fr][0];
}
fr++;
}
re++;
}
return ret;
}
void solve(int x)
{
int t=far(x),fr=1,re=0,tp=0;
Q[0][0]=t;Q[0][1]=0;Q[0][2]=-1;check[t]=2;
while(fr!=re){
int i;
for(i=0;i<edge[Q[re][0]].size();i++){
int tx=edge[Q[re][0]][i].en;
if(check[tx]==2)continue;
check[tx]=2;
Q[fr][0]=tx;
Q[fr][1]=Q[re][1]+edge[Q[re][0]][i].len;
Q[fr][2]=re;
if(Q[fr][1]>Q[tp][1])tp=fr;
fr++;
}
re++;
}
int len=Q[tp][1],tx=0;
while(Q[tp][2]!=-1){
if(Q[tp][1]*2>len)tx=Q[tp][1];
else{tx=min(tx,len-Q[tp][1]);break;}
tp=Q[tp][2];
}
if(tx)Y[tl]=tx;tl++;
inl=max(inl,len);
}
int main()
{
scanf("%d%d%d",&N,&M,&L);
int i;
for(i=1;i<=M;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
edge[x+1].push_back(line(y+1,z));
edge[y+1].push_back(line(x+1,z));
}
for(i=1;i<=N;i++){
if(check[i])continue;
solve(i);
}
sort(Y,Y+tl);
if(tl==1){printf("%d",inl);return 0;}
if(tl==2)printf("%d",max(inl,L+Y[tl-1]+Y[tl-2]));
else printf("%d",max(inl,max(L+Y[tl-1]+Y[tl-2],2*L+Y[tl-2]+Y[tl-3])));
return 0;
}
Compilation message
dreaming.cpp: In function 'int far(int)':
dreaming.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<edge[Q[re][0]].size();i++){
~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void solve(int)':
dreaming.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<edge[Q[re][0]].size();i++){
~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:64:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(tx)Y[tl]=tx;tl++;
^~
dreaming.cpp:64:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(tx)Y[tl]=tx;tl++;
^~
dreaming.cpp: In function 'int main()':
dreaming.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&N,&M,&L);
~~~~~^~~~~~~~~~~~~~~~~~~
dreaming.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~
/tmp/ccddKJW6.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccqsenh8.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccqsenh8.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
