这是 TLE 的 $70$ 分代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3000;
const int M=10000;
int n,m;
int u,v;
double w;
struct Edge{
	int v;
	double w;
	int next;
}e[(M<<1)+5];
int head[N+5],cnt;
void add(int u,int v,double w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
	return ;
}
double dis[N+5];
bitset<N+5> vis;
bool SPFA(int x,double val){
	vis[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		double w=e[i].w;
		if(dis[x]+w-val<dis[v]){
			dis[v]=dis[x]+w-val;
			if(vis[v]||SPFA(v,val))
				return 1;
		}
	}
	vis[x]=0;
	return 0;
}
bool check(double val){
	vis=0;
	for(int i=1;i<=n;i++)
		dis[i]=1e30;
	dis[1]=0;
	return SPFA(1,val);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	double l=1e30,r=-1e30;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		l=min(l,w),r=max(r,w);
	}
	while(r-l>=1e-9){
		double mid=(l+r)/2.0;
		if(check(mid))
			r=mid;
		else
			l=mid;
	}
	cout<<fixed<<setprecision(8)<<l<<"\n";
	return 0;
}

这是 $100$ 分的代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3000;
const int M=10000;
int n,m;
int u,v;
double w;
struct Edge{
	int v;
	double w;
	int next;
}e[(M<<1)+5];
int head[N+5],cnt;
void add(int u,int v,double w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
	return ;
}
double dis[N+5];
bitset<N+5> vis;
bool SPFA(int x,double val){
	vis[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		double w=e[i].w;
		if(dis[x]+w-val<dis[v]){
			dis[v]=dis[x]+w-val;
			if(vis[v]||SPFA(v,val))
				return 1;
		}
	}
	vis[x]=0;
	return 0;
}
bool check(double val){
	vis=0;
	for(int i=1;i<=n;++i)
		dis[i]=0;
	dis[1]=0;
	for(int i=1;i<=n;i++)
		if(SPFA(i,val))
			return 1;
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	double l=1e30,r=-1e30;
	for(int i=1;i<=m;++i){
		cin>>u>>v>>w;
		add(u,v,w);
		l=min(l,w),r=max(r,w);
	}
	while(r-l>=1e-9){
		double mid=(l+r)/2.0;
		if(check(mid))
			r=mid;
		else
			l=mid;
	}
	cout<<fixed<<setprecision(8)<<l<<"\n";
	return 0;
}

为什么改了下 check 函数中的初始化就对了呢？求大佬讲解。