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

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100001;
int n,m,ans;
struct node{
	int to,c,l;
	bool operator<(const node& x)const{return c>x.c;}
};
vector<node> e[MAXN];
int dis[MAXN],l[MAXN];
bool vis[MAXN];
void in(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,x;
		cin>>a>>b>>x>>l[i];
		e[a].push_back({b,x,l[i]});
		e[b].push_back({a,x,l[i]});
	}
}
int d(int lt){
	priority_queue<node> q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	q.push(node{1,0,lt});
	while(!q.empty()){
		int u=q.top().to;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++){
		    node x=e[u][i];
		    if(x.l>=lt&&dis[x.to]>dis[u]+x.c){
		 	   dis[x.to]=dis[u]+x.c;
		 	   q.push({x.to,dis[x.to],lt});
		    }
        }
	}
	return dis[n];
}
int main(){
    freopen("pump.in","r",stdin);
    freopen("pump.out","w",stdout);
	in();
	for(int i=1;i<=m;i++) ans=max(ans,l[i]*100*100*100/d(l[i]));
	cout<<ans<<endl;
	return 0;
}