fork download
copy 
  1. // USACO 2019 December Contest, Gold
  2. //Problem 1. Milk Pumping
  3. #include<bits/stdc++.h>
  4. #define int long long
  5. using namespace std;
  6. void usaco(){
  7. 	freopen("pump.in","r",stdin);
  8. 	freopen("pump.out","w",stdout);
  9. }
  10. const int N=2e5+5;
  11. int n,m,dis[N];
  12. vector<tuple<int,int,int>> a[N]; 
  13. int dij(){
  14. 				  //      d   f   s   x
  15. 	priority_queue<tuple<int,int,int,int>>q;
  16. 	q.push({0,0,1e18,1}); dis[1]=0;
  17. 	while(!q.empty()){
  18. 		auto [d,f,s,x]=q.top(); q.pop(); d=-d;
  19. 		if(d>dis[x]) continue; 
  20. 		for(auto [i,ff,ss]:a[x]){
  21. 			if(dis[i]<(int)(min(s,ss)/(f+ff))){
  22. 				dis[i]=(int)(min(s,ss)/(f+ff));
  23. 				q.push({-dis[i],f+ff,min(s,ss),i});
  24. 			}
  25. 		}
  26. 	}
  27. 	return dis[n];
  28. }
  29. signed main() {
  30. 	ios::sync_with_stdio(false); cin.tie(nullptr);
  31. 	usaco();
  32. 	cin>>n>>m;
  33. 	for(int i=0;i<m;i++){
  34. 		int u,v,f,s; cin>>u>>v>>f>>s; s*=1000000;
  35. 		a[u].push_back({v,f,s});
  36. 		a[v].push_back({u,f,s});
  37. 	}
  38. 	cout<<dij();
  39. }
  40.  
Success #stdin #stdout 0.01s 9380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FhPOc2
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!