100pts是帮别人交的代码

#include<bits/stdc++.h>
#define int long long
#define INF 100000000000000
#define MAXN 210000
using namespace std;
bool vis[MAXN];
int dis1[MAXN],dis2[MAXN],up[MAXN];
int head[MAXN],nxt[MAXN],val[MAXN],to[MAXN],tot;
vector<int>link[MAXN],Fin;
set<int>son[MAXN];
int n,m,l,cnt,ans,Max_dis;
void add(int u,int v,int w)
{
	 tot++;
	 to[tot]=v;
	 nxt[tot]=head[u];
	 head[u]=tot;
	 val[tot]=w;
}
int dfs_down(int now,int fa)
{ 
//     cout<<"now: "<<now<<endl;
     vis[now]=true;
     link[cnt].push_back(now);
     dis1[now]=dis2[now]=0;
     for(int i=head[now];i;i=nxt[i])
     {
     	 int y=to[i],w=val[i];
     	 if(y==fa) continue;
     	 int dis=dfs_down(y,now)+w;
//     	 cout<<"dis: "<<now<<" "<<y<<" "<<dis<<endl;
     	 if(dis>dis1[now])
     	 {
     	 	dis2[now]=dis1[now];
     	 	dis1[now]=dis;
     	 	son[now].clear();
     	 	son[now].insert(y);
		 }
		 else if(dis==dis1[now])
		 {
		 	  son[now].insert(y);
		 }
		 else if(dis>dis2[now])
		 {
		 	  dis2[now]=dis;
		 }
	 }
	 if(dis1[now]==-INF&&dis2[now]==-INF) dis1[now]=dis2[now]=0;
     Max_dis=max(Max_dis,dis1[now]+dis2[now]);
	 return dis1[now];
}
void dfs_up(int now,int fa)
{
	 for(int i=head[now];i;i=nxt[i])
	 {
	 	 int y=to[i],w=val[i];
	 	 if(y==fa) continue;
	 	 if(son[now].count(y)) up[y]=max(up[now],dis2[now])+w;
	 	 else up[y]=max(up[now],dis1[now])+w;
	 	 dfs_up(y,now);
	 }
}
bool cmp(int a,int b)
{
	 return a>b;
}
int u,v,w;
signed main()
{
	cin>>n>>m>>l;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		u++;
		v++;
		add(u,v,w);
	    add(v,u,w);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
		   ++cnt;
           dfs_down(i,i);
           dfs_up(i,i);
           int res=INF;
           for(int j=0;j<link[cnt].size();j++)
           {
           	   res=min(res,max(dis1[link[cnt][j]],up[link[cnt][j]]));
		   }
		   Fin.push_back(res);
		}
	}
	sort(Fin.begin(),Fin.end(),cmp);
    ans=Max_dis;
	if(cnt>1)
    {
       ans=max(ans,Fin[0]+Fin[1]+l);
	}
	if(cnt>2)
	{
	   ans=max(ans,Fin[1]+Fin[2]+l+l);
	}
	cout<<ans<<endl;
}