#include<cstdio>
#include<vector>
#include<algorithm>
#include "dreaming.h"
struct AA{
int to,cost;
};
std::vector<AA>G[100002];
int ans,i,m,t,st[100002],back[100002],backlen[100002],pos,len,K;
bool v[100002],vv[100002];
void dfs(int x,int l)
{
for(int j=0;j<G[x].size();j++)
{
AA u=G[x][j];
if(!v[u.to])
{
if(m<=l+u.cost)
{
pos=u.to;m=l+u.cost;
}
v[u.to]=1;
dfs(u.to,l+u.cost);
}
}
}
void dfs2(int x,int l)
{
for(int j=0;j<G[x].size();j++)
{
AA u=G[x][j];
if(!vv[u.to])
{
if(m<=l+u.cost)
{
pos=u.to;m=l+u.cost;
}
vv[u.to]=1;
dfs2(u.to,l+u.cost);
}
else back[x]=u.to,backlen[x]=u.cost;
}
}
main()
{
for(i=0;i<M;i++)
{
G[A[i]+1].push_back({B[i]+1,T[i]});
G[B[i]+1].push_back({A[i]+1,T[i]});
}
for(i=1;i<=N;i++)
{
if(!v[i])
{
v[i]=1;
m=0;
pos=i;
dfs(i,0);
m=0;
back[pos]=-1;
vv[pos]=1;
dfs2(pos,0);
len=std::max(len,m);
K=0;st[t]=m;
while(back[pos]!=-1)
{
K+=backlen[pos];
st[t]=std::min(st[t],std::max(K,m-K));
pos=back[pos];
}
t++;
}
}
if(t==1)ans=std::max(st[0],len);
else if(t==2)ans=std::max(st[0]+st[1]+L,len);
else
{
std::sort(st,st+t);
int m1=st[t-1],m2=st[t-2],m3=st[t-3];
ans=std::max(len,m1+L+m2);
ans=std::max(ans,m2+2*L+m3);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<G[x].size();j++)
~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<G[x].size();j++)
~^~~~~~~~~~~~
dreaming.cpp: At global scope:
dreaming.cpp:45:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
dreaming.cpp: In function 'int main()':
dreaming.cpp:48:12: error: 'M' was not declared in this scope
for(i=0;i<M;i++)
^
dreaming.cpp:50:5: error: 'A' was not declared in this scope
G[A[i]+1].push_back({B[i]+1,T[i]});
^
dreaming.cpp:50:24: error: 'B' was not declared in this scope
G[A[i]+1].push_back({B[i]+1,T[i]});
^
dreaming.cpp:50:31: error: 'T' was not declared in this scope
G[A[i]+1].push_back({B[i]+1,T[i]});
^
dreaming.cpp:53:13: error: 'N' was not declared in this scope
for(i=1;i<=N;i++)
^
dreaming.cpp:77:40: error: 'L' was not declared in this scope
else if(t==2)ans=std::max(st[0]+st[1]+L,len);
^
dreaming.cpp:82:23: error: 'L' was not declared in this scope
ans=std::max(len,m1+L+m2);
^
