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

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

const int N=6e3+100;

int n,m;
int head[N],nxt[N],to[N],fy[N],iu[N],cnt;
int dis[N],tot[N],ans;
bool check[N];
queue<int> q;

void add(int a,int b,int c,int d){
	to[++cnt]=b;
	nxt[cnt]=head[a];
	fy[cnt]=c;
	iu[cnt]=d;
	head[a]=cnt;
}

void spfa(){
	for (int tf=1;tf<=1000;tf++){
		for (int i=1;i<=n;i++) dis[i]=0x3f3f3f3f,check[i]=0;
		dis[1]=0;check[1]=1;
		q.push(1);
		while(!q.empty()){
			int u=q.front();q.pop();check[u]=0;
			for (int i=head[u];i;i=nxt[i]){
				int v=to[i],w=fy[i],y=iu[i];
				if (y<tf) continue;
				if (dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					if (!check[v]){
						check[v]=1;
						q.push(v);
					}
				}
			}
		}
		if(dis[n]!=0x3f3f3f3f) ans=max(ans,tf*1000000/dis[n]);
	}
}

int main(){
	freopen("pump.in","r",stdin);
	freopen("pump.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;i++){
		int a,b,c,d;
		scanf("%d %d %d %d",&a,&b,&c,&d);
		add(a,b,c,d);add(b,a,c,d);
	}
	ans=0;
	spfa();
	printf("%d",ans);
	return 0;
}