C++14(g++5.4) 解法, 执行用时: 44ms, 内存消耗: 4200K, 提交时间: 2020-04-23 10:41:26

#include<bits/stdc++.h>
using namespace std;
const int MX=1e5+9;
const double eps=1e-9;
int n,m,ok=0,vis[MX];
double dis[MX];
struct node{
    int v;
    double val;
};
vector<node> vec[MX];

void spfa(int u,double val){
    if( ok )
        return ;
    vis[u]=1;
    for( int i=0 ; i<vec[u].size() ; i++ ){
        int v=vec[u][i].v;
        double w=vec[u][i].val;
        if( dis[v]>dis[u]+w-val ){
            dis[v]=dis[u]+w-val;
            if( vis[v] ){
                ok=1;
                return ;
            }
            spfa(v,val);
            if( ok )
                return ;
        }
    }
    vis[u]=0;
}

int panduan(double val){
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    ok=0;
    for( int i=1 ; i<=n ; i++ ){
        spfa(i,val);
        if( ok )
            return 1;
    }
    return 0;
}

int main()
{
//    freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&m);
    double val;
    for( int i=1,u,v ; i<=m ; i++ ){
        scanf("%d %d %lf",&u,&v,&val);
        vec[u].push_back({v,val});
    }
    double l=0,r=1000000,ans;
    while( l+eps<r ){
        double mid=(l+r)/2.0;
        if( panduan(mid) ){
            ans=mid;
            r=mid-eps;
        }
        else
            l=mid+eps;
    }
    printf("%.08lf\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 80ms, 内存消耗: 660K, 提交时间: 2020-09-23 11:31:54

#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;
				if(vis[y]) continue;
				vis[y] = 1;q.push(y);
				inq[y]++;if(inq[y] > 20) return false;
			}
		}
	}
	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;
}