Luo Valley P5837 [USACO19DEC] Milk Pumping G (Dijkstra, Score Plan)

Transmitter


解题思路

Score planning problem: Maximize the ratio.
You can enumerate the traffic, and then Dijkstra run the shortest circuit to find the fee, update the answer.

ac code

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<set>using namespace std;const int maxn=1005;int n,m,dis[maxn],p[maxn],cnt;long long ans;struct node{	int v,next,w,f;}e[maxn*2];void insert(int u,int v,int w,int f){	cnt++;	e[cnt].v=v;	e[cnt].f=f;	e[cnt].w=w;	e[cnt].next=p[u];	p[u]=cnt;}int dij(int x){	memset(dis,0x3f,sizeof(dis));	set<pair<int,int> > s;	dis[1]=0;	s.insert(make_pair(0,1));	while(!s.empty()){		int u=s.begin()->second;		s.erase(s.begin());		if(u==n) return dis[n];		for(int i=p[u];i!=-1;i=e[i].next){			if(e[i].f<x) continue;			int v=e[i].v;			if(dis[v]>dis[u]+e[i].w){				s.erase(make_pair(dis[v],v));				dis[v]=dis[u]+e[i].w;				s.insert(make_pair(dis[v],v));			}		}	}	return dis[n];}int main(){	ios::sync_with_stdio(false);	memset(p,-1,sizeof(p));	cin>>n>>m;	for(int i=1;i<=m;i++){		int u,v,c,f;		cin>>u>>v>>c>>f;		insert(u,v,c,f);		insert(v,u,c,f);	}	for(int i=1;i<=1000;i++){		ans=max(ans,(long long)(1000000*i/dij(i)));	}	cout<<ans;	return 0;}