分析

说句人话，题目的意思是要我们求这个 ，这个类似分数规划的式子，先钦定答案 ，那么 满足 ，通分移项 ，那么二分 ，而新图边权为 当图中出现负环时，那么这个是一个可行的 。但是判负环的时间复杂度较高，加上二分可能会超时，所以当我们入队超过 一个常数。虽然正确性出现了问题，但是数据较难构造，然后就过了。

• 对于正确解法，应该使用 实现的判负环，可以通过。我这里偷懒就没写了。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  const int N = 5e5 + 10,inf = 2e9;
  int n,m,head[N],ecnt,inq[N],vis[N];
  struct Edge{int to,nxt;double w;}e[N];
  double dis[N];
  void add(int x,int y,double z) {
    e[++ecnt].to = y;e[ecnt].nxt = head[x];head[x] = ecnt;e[ecnt].w = z;
  }
  int read() {
    int x=0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;    
  }
  queue<int> q;
  bool check(double mid) {
    while(!q.empty()) q.pop();    
    for(int i = 1;i <= n;i++) dis[i] = 0,vis[i] = 1,inq[i] = 1,q.push(i);
    while(!q.empty()) {
        int x = q.front();q.pop();vis[x] = 0;
        for(int i = head[x];i;i = e[i].nxt) {
            int y = e[i].to;double w = e[i].w - mid;
            if(dis[y] - dis[x] - w > 1e-10) {
                dis[y] = dis[x] + w;
                inq[y]++;
                if(inq[y] > 20) return false;
                if(vis[y]) continue;
                vis[y] = 1;q.push(y);
  
            }
        }
    }
    return true;
  }
  int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++) {
        int a,b;double c;scanf("%d%d%lf",&a,&b,&c);
        add(a,b,1.0*c);
    }
    double l = -inf,r = inf;
    while(r - l > 1e-10) {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.8f\n",l);
    return 0;
  }