#include<bits/stdc++.h>
using namespace std;
int n,m,u,v;
int cnt[3005];
bool vis[3005];
double dist[3005];
double t,L=-5e4,R=5e4,mid;
struct node{int to;double t,now;};
vector<node> edge[3005];
bool spfa(){
	queue<int> q;
	for(int i=2;i<=n;i++) dist[i]=1e8;
	memset(cnt,0,sizeof cnt);
	memset(vis,0,sizeof vis);
	q.push(1);
	cnt[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(node y:edge[x]){
			if(dist[y.to]-(dist[x]+y.now)>0){
				dist[y.to]=dist[x]+y.now;
				cnt[y.to]++;
				if(cnt[y.to]==n) return 1;
				if(!vis[y.to]){
					vis[y.to]=1;
					q.push(y.to);
				}
			}
		}
	}
	return 0;
}
bool check(double mid){
	for(int i=1;i<=n;i++){
		for(int j=0;j<edge[i].size();j++){
			edge[i][j].now=edge[i][j].t-mid;
		}
	}
	return spfa();
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>t;
		edge[u].push_back({v,t,0});
	}
	while(1e-10<R-L){
		mid=(L+R)/2;
		if(check(mid)) R=mid;
		else L=mid;
	}
	cout<<fixed<<setprecision(8)<<R;
	return 0;
}

上面这份代码能过

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v;
int cnt[3005];
bool vis[3005];
double dist[3005];
double t,L=-1e5,R=1e5,mid;
struct node{int to;double t,now;};
vector<node> edge[3005];
bool spfa(){
	queue<int> q;
	for(int i=2;i<=n;i++) dist[i]=1e8;
	memset(cnt,0,sizeof cnt);
	memset(vis,0,sizeof vis);
	q.push(1);
	cnt[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(node y:edge[x]){
			if(dist[y.to]-(dist[x]+y.now)>0){
				dist[y.to]=dist[x]+y.now;
				cnt[y.to]++;
				if(cnt[y.to]==n) return 1;
				if(!vis[y.to]){
					vis[y.to]=1;
					q.push(y.to);
				}
			}
		}
	}
	return 0;
}
bool check(double mid){
	for(int i=1;i<=n;i++){
		for(int j=0;j<edge[i].size();j++){
			edge[i][j].now=edge[i][j].t-mid;
		}
	}
	return spfa();
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>t;
		edge[u].push_back({v,t,0});
	}
	while(1e-10<R-L){
		mid=(L+R)/2;
		if(check(mid)) R=mid;
		else L=mid;
	}
	cout<<fixed<<setprecision(8)<<R;
	return 0;
}

这份过不了

区别：L,R初始范围

为啥啊？