Milk Puming

tepyotin2

May 25th, 2025

184

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 1.87 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
struct Pipe{
int from, to, cost, flow;
bool operator<(const Pipe& a) const{
return flow<a.flow;
}
};
struct Node{
int to, weight;
bool operator>(const Node& a) const{
return weight>a.weight;
}
};
int n, m;
int ans = 0;
int main(){
//freopen("milkpump.in", "r", stdin);
cin >> n >> m;
vector<Pipe> pipe(m);
for(int i=0; i<m; i++){
cin >> pipe[i].from >> pipe[i].to >> pipe[i].cost >> pipe[i].flow;
//cout << "i: " << i << " || " << pipe[i].from << ", " << pipe[i].to << ", " << pipe[i].cost << ", " << pipe[i].flow << '\n';
}
sort(pipe.begin(), pipe.end());
//cout << pipe[0].flow << '\n';
for(int i=0; i<m; i++){
int thresh = pipe[i].flow;
vector<vector<Node>> con(n+1);
priority_queue<Node, vector<Node>, greater<Node>> pq;
for(int j=i; j<m; j++){
//cout << "j: " << j << " || " << pipe[j].flow << '\n';
con[pipe[j].from].push_back({pipe[j].to, pipe[j].cost});
con[pipe[j].to].push_back({pipe[j].from, pipe[j].cost});
//con[pipe[j].from].push_back(pipe[pipe[j].to]);
//con[pipe[j].to].push_back(pipe[pipe[j].from]);
}
pq.push({1, 0});
vector<int> dist(n+1, INT_MAX);
dist[1] = 0;
while(!pq.empty()){
Node cur = pq.top();
pq.pop();
int node = cur.to;
int weight = cur.weight;
//cout << "node: " << node << ", weight: " << weight << '\n';
if(weight>dist[node]) continue;
for(Node v: con[node]){
//cout << "HI" << '\n';
//cout << "v.to: " << v.to << ", v.weight: " << v.weight << '\n';
if(dist[v.to]>dist[node]+v.weight){
//cout << "HI" << '\n';
dist[v.to] = dist[node]+v.weight;
pq.push({v.to, dist[v.to]});
}
}
}
if(dist[n] != INT_MAX){
//cout << "HI" << '\n';
int val = (1000000*thresh)/dist[n];
ans = max(ans, val);
}
}
cout << ans << '\n';
return 0;
}

Add Comment

Please, Sign In to add comment