C++14(g++5.4) 解法, 执行用时: 674ms, 内存消耗: 620K, 提交时间: 2019-02-09 21:50:36

#include<stdio.h>
#include<queue>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
int n,m,xx,yy,zz,be[2100],et,c[2100];
double l,r,mi,f[2100],te;
struct edg{
	int y,ne,z;
};
edg e[20100000];
const double eps=1e-4;
inline void add_edge(int x,int y,int z){
	e[++et].y=y;
	e[et].ne=be[x];
	e[et].z=z;
	be[x]=et;
}
bool inq[2100];
queue<int> q;
inline bool che(double v){
	while (!q.empty()) q.pop();
	fo(i,1,n){
		f[i]=0;
		c[i]=0;
		inq[i]=1;
		q.push(i);
	}
	while (!q.empty()){
		xx=q.front();q.pop();inq[xx]=0;
		for(int i=be[xx];i;i=e[i].ne){
			int &y=e[i].y;
			te=f[xx]+e[i].z-v;
			if (te<f[y]){
				f[y]=te;
				c[y]++;
				if (c[y]>=n) return 1;
				if (!inq[y]){
					inq[y]=1;
					q.push(y);
				}
			}
		}
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	l=0x7fffffff;
	fo(i,1,m){
		scanf("%d%d%d",&xx,&yy,&zz);
		add_edge(xx,yy,zz);
		if (zz>r) r=zz;
		if (zz<l) l=zz;
	}
	if (!che(r+1)){
		printf("Rinne is cute\n");
		return 0;
	}
	while (l+eps<r){
		mi=(l+r)*0.5;
		if (che(mi)) r=mi;else l=mi;
	}
	printf("%.2f\n",(l+r)*0.5);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 740K, 提交时间: 2020-03-26 10:14:35

#include<bits/stdc++.h>
using namespace std;
vector<int>R[2005];
vector<double>W[2005];
int i,j,n,m;
double D[2005];
bool V[2005]={0};
bool DFS(int x,double s)
{
	V[x]=1;
	for(int i=0;i<R[x].size();i++)
	{
		int j=R[x][i];
		if(D[j]<=D[x]+W[x][i]-s) continue;
		D[j]=D[x]+W[x][i]-s;
		if(V[j]||DFS(j,s))
		{
			V[x]=0;
			return 1;
		}
	}
	return V[x]=0;
 } 
bool judge(double M)
{
	memset(D,0,sizeof(D));
	for(int i=1;i<=n;i++)
	if(DFS(i,M)) return 1;
	return 0;
}
int main()
{
	double l,r,s,M;
	scanf("%d%d",&n,&m);
	while(m--)
	scanf("%d%d%lf",&i,&j,&s),R[i].push_back(j),W[i].push_back(s);
	l=0,r=1e9+5;
	while(r-l>0.0001)
	{
		M=(l+r)/2;
		if(judge(M)) r=M;
		else l=M;
	}
	l<=1e9?printf("%.2lf\n",l):printf("Rinne is cute\n");
	return 0;
}