90 pts 求卡常

#include <bits/stdc++.h>
using namespace std;
const int N = 20010;
const double EPS = 1e-5;
struct node{
	int nxt, v, p;
};
int n, m, p[N], sum[N];
double dis[N];
bool vis[N];
vector<node> g[N];
queue<int> q;
inline int read(){
	int res = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9'){
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res * f;
}
bool spfa(double mid){
	for(int i = 1; i <= n; i++){
		dis[i] = 0;
		sum[i] = 0;
		vis[i] = true;
		q.push(i);
	}
	while (!q.empty()){
		int x = q.front();
		q.pop();
		vis[x] = 0;
		for (int i = 0; i < g[x].size(); i++){
			int y = g[x][i].nxt; double yy = g[x][i].p * mid - g[x][i].v;
			if (dis[y] > dis[x] + yy){
				dis[y] = dis[x] + yy;
				sum[y]++;
				if (!vis[y]) q.push(y), vis[y] = 1;
				if (sum[y] > n) return 1;
			}
		}
	}
	return 0;
}
int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; i++){
		int x = read(), y = read(), v = read(), p = read();
		g[x].push_back(node{y, v, p});
	} 
	double l = 0, r	= 200, ans = -1;
	while (l <= r - EPS){
		double mid = (l + r) / 2;
		if (spfa(mid)) ans = mid, l = mid;
		else r = mid;
	}
	if (ans < 0) puts("-1");
	else printf("%.1lf", ans);
	return 0;
}