在机房的小伙伴提醒是二分之后，我想到了是判负环，所以我用spfa，而且我保持dis都是小于等于0，本以为这样就能过了，可是还是有一个点达到了3.8s左右（其他都是0.0几秒）
所以还是写了dfs版本，还是一样每次都保持dis小于等于0，当发现有一个点在栈中，你又可以更新他的dis，那么就有负环了
1 const 2 maxn=3010; 3 maxm=10010; 4 inf=99999; 5 var 6 first:array[0..maxn]of longint; 7 next,last:array[0..maxm]of longint; 8 w:array[0..maxm]of double; 9 n,m:longint; 10 11 procedure init; 12 var 13 i,x:longint; 14 begin 15 read(n,m); 16 for i:=1 to m do 17 begin 18 read(x); 19 read(last[i],w[i]); 20 next[i]:=first[x]; 21 first[x]:=i; 22 end; 23 end; 24 25 var 26 flag,vis:array[0..maxn]of longint; 27 dis:array[0..maxn]of double; 28 time,time2:longint; 29 ans:double; 30 31 function dfs(x:longint;f:double):boolean; 32 var 33 i:longint; 34 begin 35 flag[x]:=time; 36 vis[x]:=time2; 37 dis[x]:=f; 38 i:=first[x]; 39 while i<>0 do 40 begin 41 if f+w[i]-ans<=0 then 42 begin 43 if vis[last[i]]=time2 then 44 if dis[last[i]]>=f+w[i]-ans then exit(true); 45 if vis[last[i]]<>time2 then 46 if dfs(last[i],f+w[i]-ans) then exit(true); 47 end; 48 i:=next[i]; 49 end; 50 vis[x]:=time2-1; 51 exit(false); 52 end; 53 54 procedure work; 55 var 56 i:longint; 57 l,r:double; 58 f:boolean; 59 begin 60 l:=-10000001; 61 r:=-l; 62 while r-l>1e-9 do 63 begin 64 ans:=(l+r)/2; 65 inc(time); 66 f:=false; 67 for i:=1 to n do 68 if flag[i]<>time then 69 begin 70 inc(time2); 71 if dfs(i,0) then 72 begin 73 f:=true; 74 break; 75 end; 76 end; 77 if f then r:=ans 78 else l:=ans; 79 end; 80 writeln(ans:0:8); 81 end; 82 83 begin 84 init; 85 work; 86 end.