题意:有一\(n\)个点,\(m\)条边的双向图,每条边都有花费和流量,求从\(1\)~\(n\)的路径中,求\(max\frac{min(f)}{\sum c}\).

题解:对于c,一定是单源最短路,我们可以用dijkstra,但是这个最小流量不是很好搞,但是题目所给的数据范围较小,所以我们可以直接枚举最小流量,然后每次初始化数组跑dijkstra,去找大于当前最小流量的边,如果\(1\)~\(n\)有路径能走,我们每次维护答案的最小值.

代码:

struct misaka{

	int out;

	int val;

	int flow;

}p;

int n,m;

int dis[N];

bool st[N];

vector<misaka> v[N];

void dijkstra(int x){

	for(int i=1;i<=n;++i){

		dis[i]=INF;

		st[i]=false;

	}

	dis[1]=0;

	priority_queue<PII,vector<PII>,greater<PII>> h;

	h.push({0,1});

	while(!h.empty()){

		auto tmp=h.top();

		h.pop();

		int num=tmp.se;

		int dist=tmp.fi;

		if(st[num]) continue;

		st[num]=true;

		for(auto w:v[num]){

			if(x>w.flow) continue;

			int j=w.out;

			if(dist+w.val<dis[j]){

				dis[j]=dist+w.val;

				h.push({dis[j],j});

			}

		}

	}

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

  	cin>>n>>m;

  	for(int i=1;i<=m;++i){

  		int a,b;

  		cin>>a>>b;

  		cin>>p.val>>p.flow;

  		p.out=b;

  		v[a].pb(p);

  		p.out=a;

  		v[b].pb(p);

  	}

  	int ans=0;

  	for(int i=1;i<=1000;++i){

  		dijkstra(i);

  		if(dis[n]!=INF) ans=max(ans,i*1000000/dis[n]);

  	}

  	cout<<ans<<endl;

    return 0;

}