二分答案再判负环
#include<cstdio> #include<algorithm> using namespace std; int read_p,read_ca; inline int read(){ read_p=0;read_ca=getchar(); while(read_ca<'0'||read_ca>'9') read_ca=getchar(); while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar(); return read_p; } struct na{ int y,ne; double z; }b[10001]; int n,m,l[3001],r[3001],ru[3001],num=0; int x,y,z,i,j,k; double dis[3001]; const double INF=1e9; double mi=1e7,ma=0; bool bo[3001]; inline void add(){ x=read();y=read();z=read(); num++; if (!l[x]) l[x]=num;else b[r[x]].ne=num; b[num].y=y;b[num].z=(double)z;r[x]=num; if (b[num].z>ma) ma=b[num].z; if (b[num].z<mi) mi=b[num].z; } inline bool spfa(int p,double x){ bo[p]=ru[p]=1; for (int j=l[p];j;j=b[j].ne) if (ru[b[j].y]&&dis[p]+b[j].z-x<=dis[b[j].y]) return 1; for (int j=l[p];j;j=b[j].ne) if (dis[b[j].y]>dis[p]+b[j].z-x){ dis[b[j].y]=dis[p]+b[j].z-x; if (spfa(b[j].y,x)) return 1; } ru[p]=0; return 0; } inline bool run(double x){ register int i; for (i=1;i<=n;i++) dis[i]=0,bo[i]=ru[i]=0; for (i=1;i<=n;i++) if (!bo[i]) if (spfa(i,x)) return 1; return 0; } int main(){ n=read();m=read(); while (m--) add(); double l=mi,r=ma,mid; while(r-l>=1e-9){ mid=(l+r)/((double)(2.0)); if (run(mid)) r=mid;else l=mid; } printf("%.8lf",l); return 0; }