Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement