记录编号	603158	评测结果	AAAAAAAAAA
题目名称	3319. [USACO19 DEC Gold]Milk Pumping	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	0.090 s
提交时间	2025-07-09 14:52:13	内存使用	4.06 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+10,INF=0x3f3f3f3f;
int n,m,maxf=-999;
struct Edge
{
    int c,e,f;
};
vector<Edge> g[N];
double ans=-9.9;
bool vis[1005];
int d[1005];
void spfa(int s,int fm)
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    deque<int> q;
    q.push_back(s);
    vis[s]=true;
    d[s]=0;
    d[0]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop_front();
        vis[x]=0;
        for(int i=0;i<g[x].size();i++)
        {
            int y=g[x][i].c,w=g[x][i].e,fl=g[x][i].f;
            if (d[y]>d[x]+w&&fl>=fm)
            {
                d[y]=d[x]+w;
                if(!vis[y])
                {
                    if(!q.empty()&&d[y]<=d[q.front()]) q.push_front(y);
                    else q.push_back(y);
                    if(!q.empty()&&d[q.front()]>d[q.back()]) swap(q[0],q[q.size()-1]);
                    vis[y]=1;
                }
            }
        }
    }
}
int main()
{
    freopen("pump.in","r",stdin);
    freopen("pump.out","w",stdout);
    
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,w,f1;
        cin>>x>>y>>w>>f1;
        g[x].push_back({y,w,f1}),g[y].push_back({x,w,f1});
        maxf=max(maxf,f1);
    }
    for(int i=1;i<=maxf;i++)
    {
        spfa(1,i);
        ans=max(ans,floor((i*1.0/d[n])*1000000));
    }
    printf("%.0f",ans);
    return 0;
}