求调玄关

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 3010;
vector<pair<int,int>> G[N];
int dis[N];
bool vis[N];
    int n,m;
bool SPFA(int u, double mid) { 
  vis[u] = 1;
  for (auto x : G[u]) {
    int v = x.first;
    double w = x.second - mid;
    if (dis[u] + w < dis[v]) {
      dis[v] = dis[u] + w;
      if (vis[v] || SPFA(v, mid)) return 1;
    }
  }
  vis[u] = 0;
  return 0;
}

bool check(double mid) {  
  for (int i = 1; i <= n; i++) dis[i] = 0, vis[i] = 0;
  for (int i = 1; i <= n; i++)
    if (SPFA(i, mid)) return 1;
  return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    cin>>n>>m;
    for(int i = 1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back({v,w});
    }
    for(int i = 1;i<=n;i++){
        G[0].push_back({i,0});
    }
    double l = 0,r = 1e10;
    while(r-l>=1e-9){
        double mid = (l+r)/2.0;
        if(!check(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    printf("%.8lf",r);
    return 0;
}