Advertisement
tepyotin2

Milk Puming

May 25th, 2025
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Pipe{
  6.     int from, to, cost, flow;
  7.     bool operator<(const Pipe& a) const{
  8.         return flow<a.flow;
  9.     }
  10. };
  11.  
  12. struct Node{
  13.     int to, weight;
  14.     bool operator>(const Node& a) const{
  15.         return weight>a.weight;
  16.     }
  17. };
  18.  
  19. int n, m;
  20. int ans = 0;
  21.  
  22. int main(){
  23.     //freopen("milkpump.in", "r", stdin);
  24.    
  25.     cin >> n >> m;
  26.     vector<Pipe> pipe(m);
  27.     for(int i=0; i<m; i++){
  28.         cin >> pipe[i].from >> pipe[i].to >> pipe[i].cost >> pipe[i].flow;
  29.         //cout << "i: " << i << " || "  << pipe[i].from << ", " << pipe[i].to << ", " << pipe[i].cost << ", " << pipe[i].flow << '\n';
  30.     }
  31.     sort(pipe.begin(), pipe.end());
  32.     //cout << pipe[0].flow << '\n';
  33.     for(int i=0; i<m; i++){
  34.         int thresh = pipe[i].flow;
  35.         vector<vector<Node>> con(n+1);
  36.         priority_queue<Node, vector<Node>, greater<Node>> pq;
  37.         for(int j=i; j<m; j++){
  38.             //cout << "j: " << j << " || " << pipe[j].flow << '\n';
  39.             con[pipe[j].from].push_back({pipe[j].to, pipe[j].cost});
  40.             con[pipe[j].to].push_back({pipe[j].from, pipe[j].cost});
  41.             //con[pipe[j].from].push_back(pipe[pipe[j].to]);
  42.             //con[pipe[j].to].push_back(pipe[pipe[j].from]);
  43.         }
  44.         pq.push({1, 0});
  45.         vector<int> dist(n+1, INT_MAX);
  46.         dist[1] = 0;
  47.         while(!pq.empty()){
  48.             Node cur = pq.top();
  49.             pq.pop();
  50.             int node = cur.to;
  51.             int weight = cur.weight;
  52.             //cout << "node: " << node << ", weight: " << weight << '\n';
  53.             if(weight>dist[node]) continue;
  54.             for(Node v: con[node]){
  55.                 //cout << "HI" << '\n';
  56.                 //cout << "v.to: " << v.to << ", v.weight: " << v.weight << '\n';
  57.                 if(dist[v.to]>dist[node]+v.weight){
  58.                     //cout << "HI" << '\n';
  59.                     dist[v.to] = dist[node]+v.weight;
  60.                     pq.push({v.to, dist[v.to]});
  61.                 }
  62.             }
  63.         }
  64.         if(dist[n] != INT_MAX){
  65.             //cout << "HI" << '\n';
  66.             int val = (1000000*thresh)/dist[n];
  67.             ans = max(ans, val);
  68.         }
  69.     }
  70.     cout << ans << '\n';
  71.    
  72.     return 0;
  73. }
  74.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement