C++14(g++5.4) 解法, 执行用时: 142ms, 内存消耗: 888K, 提交时间: 2020-01-01 20:20:51

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 3e3+1;

struct Edge {
  int v;
  double w;
};
vector<Edge> G[MAXN];
int n, m;

bool inq[MAXN];
double dis[MAXN];

bool dfs(int s, double limit) {
  inq[s] = true;
  for (auto e: G[s]) {
    // double w = limit - e.w;
    double w = e.w - limit;
    if (dis[e.v] <= dis[s] + w) continue;
    if (inq[e.v]) return true;
    dis[e.v] = dis[s] + w;
    if (dfs(e.v, limit)) return true;
  }
  inq[s] = false;
  return false;
}

bool isValid(double limit) {
  for (int i = 1; i <= n; i++) {
    memset(dis, 0, sizeof(dis));
    memset(inq, 0, sizeof(inq));
    if (dfs(i, limit)) return true;
  }
  return false;
}

int main() {
  cin >> n >> m;
  while (m--) {
    int i, j; double w; cin >> i >> j >> w;
    G[i].push_back(Edge{j, w});
  }

  double lo = -1e7, hi = 1e7+1;
  while (hi - lo > 1e-9) {
    double mid = (lo + hi) / 2;
    if (!isValid(mid)) lo = mid;
    else hi = mid;
  }
  cout << fixed << setprecision(8) << lo << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 876K, 提交时间: 2020-05-28 10:14:53

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e3+1;
struct Edge
{
	int v;
	double w;
};
vector<Edge> G[MAXN];
int n,m;
bool inq[MAXN];
double dis[MAXN];
bool dfs(int s,double limit)
{
	inq[s]=true;
	for(auto e:G[s])
	{
		double w=e.w-limit;
		if(dis[e.v]<=dis[s]+w) continue;
		if(inq[e.v]) return true;
		dis[e.v]=dis[s]+w;
		if(dfs(e.v,limit)) return true;
	}
	inq[s]=false;
	return false;
}
bool isValid(double limit)
{
	for(int i=1;i<=n;i++)
	{
		memset(dis,0,sizeof(dis));
		memset(inq,0,sizeof(inq));
		if(dfs(i,limit)) return true; 
	}
	return false;
}
int main()
{
	cin>>n>>m;
	while(m--)
	{
		int i,j;
		double w;
		cin>>i>>j>>w;
		G[i].push_back(Edge{j,w}); 
	}
	double lo=-1e7,hi=1e7+1;
	while(hi-lo>1e-9)
	{
		double mid=(lo+hi)/2;
		if(!isValid(mid)) lo=mid;
		else hi=mid;
	}
	cout<<fixed<<setprecision(8)<<lo<<endl;
}