记录编号	603397	评测结果	AAAAAAAAAA
题目名称	3319. [USACO19 DEC Gold]Milk Pumping	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.316 s
提交时间	2025-07-11 16:15:22	内存使用	3.76 MiB

#include<iostream>
#include<set>
#include<cstring>
using namespace std;

const int MAXN = 1e4 + 5;
const int MAXM = 1e4 + 5;
struct node{
	int to, next, len, val;
}e[MAXM * 2];
int n, m, xx, d[MAXN];
int h[MAXN], tot = 0;
int x[MAXN];
void add(int x, int y, int len, int val){
	e[++ tot] = {y,h[x],len,val};
	h[x] = tot;
}
set<pair<int,int> > heap;

int diji(int now){
	memset(d,0x3f3f3f3f,sizeof(d));
	d[1] = 0;
	heap.insert({d[1], 1});
	while(!heap.empty()){
		int dis = heap.begin() -> first;
		int cnt = heap.begin() -> second;
		heap.erase(heap.begin());
		for(int i = h[cnt];i;i = e[i].next){
			int to = e[i].to;
			if(d[to] > d[cnt] + e[i].len && e[i].val >= now){
				heap.erase({d[to],to});
				d[to] = d[cnt] + e[i].len;
				heap.insert({d[to],to});
			}
		}
	}
	return d[n];
}

int main(){
	freopen("pump.in","r",stdin);
	freopen("pump.out","w",stdout);
	cin >> n >> m;
	for(int i = 1;i <= m;i ++){
		int u, v, w, vs;
		cin >> u >> v >> w >> vs;
		x[i] = vs;
		add(u, v, w, vs);
		add(v, u, w, vs);
	}
	int ans = -1;
	for(int i = 1;i <= 1005;i ++){
		int dis = diji(i);
		if(dis != 0x3f3f3f3f){
			ans = max(1000000 * i / dis,ans);
		}
	}
	cout << ans << "\n";
	return 0;
}