目前目测过两遍程序,应该没有什么低级问题 可能是实现的思路有些问题,求大佬指点

#include <bits/stdc++.h>
#define inf 9223372036854775807LL
#define mod 1000000007
//#pragma GCC optimize(2)
#define int long long
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n,m;
long long sum=0,ans=inf;
pair<pair<int,int>,pair<int,int> > edge[300005];
int pre[100005];
int h[100005],e[600005],w[600005],ne[600005],idx;
bool tree[600005];
int depth[100005],fa[100005][18],dp[100005][18][2];
void add(int x,int y,int z)
{
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
	e[idx]=x,w[idx]=z,ne[idx]=h[y],h[y]=idx++;
}
int fnd(int x)
{
	if(pre[x]!=x) pre[x]=fnd(pre[x]);
	return pre[x];
}
void kruskal()
{
	sort(edge+1,edge+m+1);
	for(int i=1;i<=n;++i)
		pre[i]=i;
	for(int i=1;i<=m;++i)
	{
		int fx=fnd(edge[i].second.first),fy=fnd(edge[i].second.second);
		if(fx!=fy)
		{
			pre[fx]=fy;
			sum+=edge[i].first.first;
			tree[edge[i].first.second*2]=tree[edge[i].first.second*2+1]=1;
		}
	}
}
void bfs()
{
	for(int i=0;i<=n;++i)
	{
		depth[i]=inf;
		for(int k=0;k<=17;++k)
			dp[i][k][0]=dp[i][k][1]=-inf;
	}
	depth[0]=0,depth[1]=1;
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(int i=h[t];~i;i=ne[i])
		{
			int j=e[i];
			if(depth[j]>depth[t]+1&&tree[i])
			{
				depth[j]=depth[t]+1;
				q.push(j);
				fa[j][0]=t;
				dp[j][0][0]=w[i];
				for(int k=1;k<=17;++k)
					fa[j][k]=fa[fa[j][k-1]][k-1];
			}
		}
	}
	for(int k=1;k<=17;++k)
	{
		for(int i=1;i<=n;++i)
		{
			if(dp[i][k-1][0]>dp[i][k][0])
			{
				dp[i][k][1]=dp[i][k][0];
				dp[i][k][0]=dp[i][k-1][0];
			}
			else if(dp[i][k-1][0]!=dp[i][k][0]&&dp[i][k-1][0]>dp[i][k][1])
				dp[i][k][1]=dp[i][k-1][0];
			if(dp[i][k-1][1]>dp[i][k][0])
			{
				dp[i][k][1]=dp[i][k][0];
				dp[i][k][0]=dp[i][k-1][1];
			}
			else if(dp[i][k-1][1]!=dp[i][k][0]&&dp[i][k-1][1]>dp[i][k][1])
				dp[i][k][1]=dp[i][k-1][1];
			if(dp[fa[i][k-1]][k-1][0]>dp[i][k][0])
			{
				dp[i][k][1]=dp[i][k][0];
				dp[i][k][0]=dp[fa[i][k-1]][k-1][0];
			}
			else if(dp[fa[i][k-1]][k-1][0]!=dp[i][k][0]&&dp[fa[i][k-1]][k-1][0]>dp[i][k][1])
				dp[i][k][1]=dp[fa[i][k-1]][k-1][0];
			if(dp[fa[i][k-1]][k-1][1]>dp[i][k][0])
			{
				dp[i][k][1]=dp[i][k][0];
				dp[i][k][0]=dp[fa[i][k-1]][k-1][1];
			}
			else if(dp[fa[i][k-1]][k-1][1]!=dp[i][k][0]&&dp[fa[i][k-1]][k-1][1]>dp[i][k][1])
				dp[i][k][1]=dp[fa[i][k-1]][k-1][1];
		}
	}
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	read(n);read(m);
	memset(h,-1,sizeof(h));
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		read(x);read(y);read(z);
		add(x,y,z);
		edge[i]=make_pair(make_pair(z,i-1),make_pair(x,y));
	}
	kruskal();
	bfs();
	for(int i=1;i<=m;++i)
		if(!tree[edge[i].first.second*2])
		{
			int a=edge[i].second.first,b=edge[i].second.second;
			if(a==b) continue;
			int max1=-inf,max2=-inf;
			if(depth[a]<depth[b]) swap(a,b);
			for(int k=17;k>=0;--k)
				if(depth[fa[a][k]]>depth[b])
				{
					if(dp[a][k][0]>max1)
					{
						max2=max1;
						max1=dp[a][k][0];
					}
					else if(dp[a][k][0]!=max1&&dp[a][k][0]>max2)
						max2=dp[a][k][0];
					if(dp[a][k][1]>max1)
					{
						max2=max1;
						max1=dp[a][k][1];
					}
					else if(dp[a][k][1]!=max1&&dp[a][k][1]>max2)
						max2=dp[a][k][1];
					a=fa[a][k];
				}
			if(a!=b)
			{
				for(int k=17;k>=0;--k)
					if(fa[a][k]!=fa[b][k])
					{
						if(dp[a][k][0]>max1)
						{
							max2=max1;
							max1=dp[a][k][0];
						}
						else if(dp[a][k][0]!=max1&&dp[a][k][0]>max2)
							max2=dp[a][k][0];
						if(dp[a][k][1]>max1)
						{
							max2=max1;
							max1=dp[a][k][1];
						}
						else if(dp[a][k][1]!=max1&&dp[a][k][1]>max2)
							max2=dp[a][k][1];
						a=fa[a][k];
						if(dp[b][k][0]>max1)
						{
							max2=max1;
							max1=dp[b][k][0];
						}
						else if(dp[b][k][0]!=max1&&dp[b][k][0]>max2)
							max2=dp[b][k][0];
						if(dp[b][k][1]>max1)
						{
							max2=max1;
							max1=dp[b][k][1];
						}
						else if(dp[b][k][1]!=max1&&dp[b][k][1]>max2)
							max2=dp[b][k][1];
						b=fa[b][k];
					}
				if(dp[a][0][0]>max1)
				{
					max2=max1;
					max1=dp[a][0][0];
				}
				else if(dp[a][0][0]!=max1&&dp[a][0][0]>max2)
					max2=dp[a][0][0];
				if(dp[a][0][1]>max1)
				{
					max2=max1;
					max1=dp[a][0][1];
				}
				else if(dp[a][0][1]!=max1&&dp[a][0][1]>max2)
					max2=dp[a][0][1];
				a=fa[a][0];
				if(dp[b][0][0]>max1)
				{
					max2=max1;
					max1=dp[b][0][0];
				}
				else if(dp[b][0][0]!=max1&&dp[b][0][0]>max2)
					max2=dp[b][0][0];
				if(dp[b][0][1]>max1)
				{
					max2=max1;
					max1=dp[b][0][1];
				}
				else if(dp[b][0][1]!=max1&&dp[b][0][1]>max2)
					max2=dp[b][0][1];
				b=fa[b][0];
			}
			if(max1>-inf&&max1!=w[edge[i].first.second*2])
				ans=min(ans,sum-max1+w[edge[i].first.second*2]);
			else if(max2>-inf&&max2!=w[edge[i].first.second*2])
				ans=min(ans,sum-max2+w[edge[i].first.second*2]);
		}
	writeln(ans);
	return 0;
}