#include<bits/stdc++.h>
#define MAX_N 100005
#define pb push_back
#define inf 0x7fffffff
using namespace std;
struct node{
int y,cost;
};
struct cmp{
bool operator()(node x,node y){
if(x.cost==y.cost) return x.y<y.y;
return x.cost>y.cost;
}
};
int N,M,L,an,b[MAX_N],bn,ans;
bool c1[MAX_N],c2[MAX_N],c3[MAX_N];
node arr[MAX_N],X,Y;
vector<node> net[MAX_N];
set<node,cmp> S;
void is_far(int x,int cost){
int sz;
node y;
c1[x]=true;
sz=net[x].size();
if(X.cost<cost){
X.cost=cost;
X.y=x;
}
while(sz--){
y=net[x][sz];
if(c1[y.y]) continue;
is_far(y.y,cost+y.cost);
}
}
void find_Diameter(int x,int cost){
int sz;
node y;
c2[x]=true;
sz=net[x].size();
if(Y.cost<cost){
Y.cost=cost;
Y.y=x;
}
while(sz--){
y=net[x][sz];
if(c2[y.y]) continue;
find_Diameter(y.y,cost+y.cost);
}
}
int make_arr(int x){
int sz,maxx=0,k;
bool z;
node y;
c3[x]=true;
sz=net[x].size();
if(sz==1 && x==Y.y){
arr[an].y=0;
arr[an++].cost=0;
return -1;
}
while(sz--){
y=net[x][sz];
if(c3[y.y]) continue;
y.y=make_arr(y.y);
if(y.y==-1){
z=true;
k=y.cost;
continue;
}
y.y+=y.cost;
maxx=max(maxx,y.y);
}
if(!z) return maxx;
arr[an].y=maxx;
arr[an++].cost=k;
return -1;
}
int main(){
int i,j,x,y,z,cost;
node p;
scanf("%d %d %d",&N,&M,&L);
for(i=0;i<M;i++){
scanf("%d %d %d",&x,&y,&cost);
p.y=y;p.cost=cost;
net[x].pb(p);
p.y=x;
net[y].pb(p);
}
for(i=0;i<N;i++){
if(c1[i]) continue;
X.y=X.cost=0;
is_far(i,0);
ans=max(ans,X.cost);
Y.y=Y.cost=0;
find_Diameter(X.y,0);
ans=max(ans,Y.cost);
an=0;
S.clear();
x=make_arr(X.y);
x=0;
z=inf;
for(j=1;j<an;j++){
x+=arr[j].cost;
p.y=j;
p.cost=x+arr[j].y;
S.insert(p);
}
x=0;
y=0;
for(j=0;j<an;j++){
x+=arr[j].cost;
y+=arr[j].cost;
while(!S.empty()){
p=(*S.begin());
if(p.y<=j) S.erase(p);
else break;
}
x=max(x,arr[j].y);
if(!S.empty()){
p=(*S.begin());
z=min(max(x,p.cost-y),z);
}else z=min(z,x);
}
b[bn++]=z;
}
sort(b,b+bn);
if(bn>=2){
x=b[bn-1];
y=b[bn-2];
ans=max(ans,x+y+L);
}
if(bn>2){
x=b[bn-2];
y=b[bn-3];
ans=max(ans,x+y+2*L);
}
printf("%d\n",ans);
return 0;
}
Compilation message
dreaming.cpp: In function 'int main()':
dreaming.cpp:81:7: 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:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&x,&y,&cost);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int make_arr(int)':
dreaming.cpp:75:16: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
arr[an++].cost=k;
~~~~~~~~~~~~~~^~
/tmp/ccRwNPpl.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cceocC4r.o:grader.c:(.text.startup+0x0): first defined here
/tmp/cceocC4r.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
