记录编号	603145	评测结果	AAAAAAAAAA
题目名称	3319. [USACO19 DEC Gold]Milk Pumping	最终得分	100
用户昵称	二乾五	是否通过	通过
代码语言	C++	运行时间	0.056 s
提交时间	2025-07-09 12:26:24	内存使用	3.79 MiB

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)
#define N 1005
#define pll pair<ll,ll>

struct tube{
    ll to,c,f;
};

ll n,m,disc[N],disf[N];
bool vis[N];
vector<vector<tube>>a(N);

int main(){
    // #ifndef bendibianyi
    // #ifndef ONLINE_JUDGE
        freopen("pump.in" ,"r",stdin );
        freopen("pump.out","w",stdout);
    // #endif
    // #endif
    cin>>n>>m;
    foru(i,1,m){
        ll u,v,c,f;
        cin>>u>>v>>c>>f;
        a[u].push_back({v,c,f});
        a[v].push_back({u,c,f});
    }
    foru(i,2,n){
        disc[i]=INT_MAX;
        disf[i]=0;
    }
    disf[1]=INT_MAX;
    disc[1]=0;
    foru(i,1,n){
        ll u=0,maxc=INT_MAX,maxf=0;
        foru(j,1,n){
            if(!vis[j]&&(maxf*1.0/(1.0*maxc))<(disf[j]*1.0/(1.0*disc[j]))){
                maxf=disf[j];
                maxc=disc[j];
                u=j;
            }
        }
        vis[u]=1;
        for(auto v:a[u]){
            if(disf[v.to]*1.0/disc[v.to]<min(disf[u],v.f)*1.0/(v.c+disc[u])){
                disf[v.to]=min(disf[u],v.f);
                disc[v.to]=v.c+disc[u];
            }
        }
    }
    cout<<(ll)floor(disf[n]*1000000.0/disc[n]);
    return 0;
}