AC39,WA17求佬帮忙看看
查看原帖
AC39,WA17求佬帮忙看看
596254
ZXLcoder楼主2023/10/16 16:33
#include <bits/stdc++.h>
using namespace std;
#define accelerate ios::sync_with_stdio(false),cin.tie(0);
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define double long double
#define ufor(i,st,en) for(int i=st;i<=en;i++)
#define dfor(i,en,st) for(int i=en;i>=st;i--)
#define mp(x,y) make_pair(x,y)
#define pb(x) emplace_back(x)
#define vi vector<int>
#define vii vector<vi>
#define RE return 0;
const int N=2e5+1000;
int n,m,k,T,z,q;
int d[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int dx[]={0,0,-1,0,1},dy[]={0,-1,0,1,0};
void fixd(int x){
    cout<<setiosflags(ios::fixed)<<setprecision(x);
}
vector<array<int,3> >v[N<<3];
int b[N],c[N];
double f[N];
bool vis[N];
void solve(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y,b,c;
		cin>>x>>y>>b>>c;
		v[x].emplace_back(array<int,3>{y,b,c});
	}
	vis[1]=1;
	for(int i=1;i<=n;i++){
		if(!vis[i]) continue;
		for(auto it:v[i]){
			vis[it[0]]=1;
			double ff=1.0*(b[i]+it[1])/(c[i]+it[2]);
			if(ff>f[it[0]]){
				f[it[0]]=ff;
				b[it[0]]=b[i]+it[1];
				c[it[0]]=c[i]+it[2];
			}
		}
	}
	cout<<1.0*b[n]/c[n];
}
signed main(){
    accelerate;
    fixd(15);
    T=1;
    while(T--) solve();
    return 0;
}
2023/10/16 16:33
加载中...