Untitled
#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