Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
1.9 kB
0
Indexable
Never
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#ifdef ONLINE_JUDGE
#define debug(x...)
#define testcase(tc)
#else
#include "../debug.h"
#endif

#define int long long int
#define tp3(T) tuple<T,T,T>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pr(x) cout << x << endl
#define yesno(x) cout << ((x) ? "YES\n" : "NO\n")
const int N = 300300, MOD = 1000000009, INF = 1e5;

template <class T> bool ckmin(T &a, const T &b) {return b < a ? a = b, 1 : 0;}
template <class T> bool ckmax(T &a, const T &b) {return b > a ? a = b, 1 : 0;}
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n,m;
	cin >> n >> m;
	
	vector<vector<pair<int,pair<int,int>>>> adj(n + 1);
	for(int i = 1; i <= m; ++i){
		int u,v,b,c;
		cin >> u >> v >> b >> c;
		adj[u].push_back({v,{b,c}});
	}
	debug(adj);
	vector<long double> dp(n + 1);
	auto dfs = [&](long double mid) -> bool{
		for(int i = 1; i <= n; ++i)
			dp[i] = -1e18;
		dp[1] = 0;
		for(int i = 1; i <= n; ++i){
			for(auto p : adj[i]){
				int v = p.first, b = p.second.first, c = p.second.second;
				//debug(i, v, b, c);
				dp[v] = max(dp[v], dp[i] + b - c * mid);
			}
		}
		return dp[n] >= 0;
	};
	double lo = 0.0, high = 200200, ans = 0;
	
	for(int i = 0; i < 100; i++){
		double mid = (high - lo)/2;
		bool ok = dfs(mid);
		//debug(ok);
		if(ok){
			lo = mid;
		}
		else{
			high = mid;
		}
	}
	
	cout << fixed << setprecision(20) << lo << endl;
	
	

	return 0;
}
Leave a Comment