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

#include<cstdio>
#include<queue>
#include<algorithm>
#define N 1005
using namespace std;
int n,m,h[N],cnt,x,y,w,f,ans;bool vis[N];
struct node{int u,w;bool operator<(node y)const{return w>y.w;}};
struct ed{int x,y,w,f;}E[N];
struct edge{int v,n,w,f;}e[N<<1];
void ad(int u,int v,int w,int f){e[++cnt]={v,h[u],w,f};h[u]=cnt;}
bool cmp(ed x,ed y){return x.f>y.f;}
int max(int x,int y){return x>y?x:y;}
int dijkstra(){
	priority_queue<node>q;
	for(int i=1;i<=n;i++)vis[i]=0;
	q.push({1,0});
	while(q.size())
	{
		node u=q.top();q.pop();
		if(vis[u.u])continue;
		vis[u.u]=1;
		if(u.u==n)return u.w;
		for(int i=h[u.u];i;i=e[i].n)
		{
			int v=e[i].v,w=u.w+e[i].w;
			if(!vis[v])q.push({v,w});
		}
	}
	return 2147483647;
}
int main(){
	freopen("pump.in","r",stdin);freopen("pump.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d%d%d",&E[i].x,&E[i].y,&E[i].w,&E[i].f);
	sort(E+1,E+m+1,cmp);
	for(int i=1;i<=m;)
	{
		int now=E[i].f;
		while(i<=m&&E[i].f==now)ad(E[i].x,E[i].y,E[i].w,E[i].f),ad(E[i].y,E[i].x,E[i].w,E[i].f),i++;
		ans=max(ans,now*1000000/dijkstra());
	}
	printf("%d",ans);
	return 0;
}