60pts求条悬赏关注

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pr;
const int MX = 1e6;
int n,m,x = 1,y,dis[10010],vis[10010],sum;
struct ed{
	int v,w,c;
};
vector<ed> e[10010];
int dijk(int mid){
	memset(dis,127,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<pr,vector<pr>,greater<pr>> h;
	h.push({0,x});
	dis[x] = 0;
	while(!h.empty()){
		pr p = h.top();
		h.pop();
		int u = p.second;
		if(vis[u]) continue;
		vis[u] = 1;
		for(ed j : e[u]){
			if(j.c < mid) continue;
			if(dis[j.v] > dis[u] + j.w){
				dis[j.v] = dis[u] + j.w;
				h.push({dis[j.v],j.v});
			}
		}
	}
	return (vis[n] == 1 ? dis[n] : 0);
}
int spfa(int mid){
	memset(vis,0,sizeof(vis));
	memset(dis,127,sizeof(dis));
	queue<int> q;
	q.push(1);
	vis[1] = 1;
	dis[1] = 0;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(ed v : e[u]){
			if(v.c < mid) continue;
			if(dis[v.v] > dis[u] + v.w){
				dis[v.v] = dis[u] + v.w;
				if(!vis[v.v]){
					vis[v.v] = 1;
					q.push(v.v);
				}
			}
		}
	}
	return dis[n];
}
int main(){
	cin >> n >> m;
	for(int i = 1;i <= m;++i){
		int u,v,c,w;
		cin >> u >> v >> w >> c;
		e[u].push_back({v,w,c});
		e[v].push_back({u,w,c});
	}
	int l = 1,r = 1e9,ans = -1;
	while(l <= r){
		int mid = ((r - l) >> 1) + l;
		y = dijk(mid);
		if(y != 0){
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	cout << int((double)ans / (double)spfa(ans) * MX);
	return 0;
}