特别好题目，使我脑子旋转。

为什么第8个点T了qwq

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 3010, M = 10010;
const double eps = 1e-10;
struct edge { int u, v; double w; }e[M];
int n, m, cnt[N], vis[N]; double d[N];
vector<pair<int, int> > g[N];
bool spfa(int s, double mid)
{
	fill(d + 1, d + n + 1, 1e18);
	memset(vis, 0, sizeof(vis)), memset(cnt, 0, sizeof(cnt));
	queue<int> q; d[s] = 0, vis[s] = cnt[s] = 1; q.push(s);
	while (!q.empty())
	{
		int u = q.front(); q.pop();
		vis[u] = 0;
		for (auto x : g[u])
		{
			int v = x.first; double w = x.second;
			if (d[v] > d[u] + (w - mid))
			{
				d[v] = d[u] + (w - mid);
				if (!vis[v])
				{
					if (++cnt[v] >= n) return true;
					vis[v] = 1, q.push(v);
				}
			}
		}
	} return false;
}

int main()
{
	scanf("%d%d", &n, &m); double w;
	for (int i = 1, u, v; i <= m; i++) scanf("%d%d%lf", &u, &v, &w), g[u].push_back({v, w});
	double l = -1e7, r = 1e7;
	while (r - l > eps)
	{
		double mid = (l + r) / 2;
		if (spfa(1, mid)) r = mid;
		else l = mid;
	} printf("%.8f\n", l);
	return 0;
}