```cpp
#include<bits/stdc++.h>
using namespace std;
namespace lyt{
#define N 3001
#define M 10001
int n,m;
double eps=1e-10;
int cnt,Head[N],Next[M],V[M];
double W[M];
void add(int u,int v,double w)
{
V[cnt]=v;
W[cnt]=w;
Next[cnt]=Head[u];
Head[u]=cnt++;
}
bool vis[N];
double dis[N];
int bo;
void SPFA(int u,double x)
{
vis[u]=1;
for(int i=Head[u];i!=-1;i=Next[i])
{
if(W[i]-x+dis[u]<dis[V[i]])
{
if(vis[V[i]])
{
bo=1;
return ;
}
dis[V[i]]=dis[u]+W[i]-x;
SPFA(V[i],x);
}
if(bo==1)
{
return ;
}
}
vis[u]=0;
}
bool check(double x)
{
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
if(dis[i]!=dis[0])
{
continue;
}
dis[i]=0;
bo=0;
SPFA(i,x);
if(bo==1)
{
return 1;
}
}
return 0;
}
void main()
{
memset(Head,-1,sizeof(Head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
double w;
scanf("%d%d%lf",&u,&v,&w);
add(u,v,w);
}
double l=-1e7,r=1e7;
while(l+eps<r)
{
double mid=(l+r)/2;
if(check(mid)==1)
{
r=mid;
}
else
{
l=mid;
}
}
printf("%.8lf\n",l);
}
}
int main()
{
lyt::main();
}
```
by lytqwq @ 2020-01-18 21:48:58
Orz 01分数规划巨捞
Orz SPFA巨捞
by 辰星凌 @ 2020-01-18 21:49:22
Orz 01分数规划巨捞
Orz SPFA巨捞
by wyhwyh @ 2020-01-18 21:49:47
心态崩了（帮帮我呀
by lytqwq @ 2020-01-18 21:51:48
问题解决，SPFA判负环时dis初始化为0
by lytqwq @ 2020-01-18 21:59:02