Problem: Examples

Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Output

6


Input




Output

Solution (in CPP):

Solution:
#include <cassert>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
#include <limits>
using namespace std;

struct MinCostFlowGraph {
private:
  using ll = long long;
  struct edge {
    int to;
    ll cap, cost;
    int r_idx;
    edge(int t, ll cap, ll cost, int r) :
      to(t), cap(cap), cost(cost), r_idx(r) {}
  };
  vector<vector<edge>> G;
  int sz;
public:
  MinCostFlowGraph(int n) : G(n), sz(n) {}

  void add_edge(int from, int to, ll cap, ll cost){
    int i = G[to].size(), i_ = G[from].size();
    G[from].emplace_back(to,cap,cost,i);
    G[to].emplace_back(from,0,-cost,i_);
  }
  ll min_cost_flow(int from, int to, ll f){
    ll ans = 0;
    while(f > 0){
      const ll INF = numeric_limits<ll>::max();
      vector<ll> dist(sz,INF);
      dist[from] = 0;
      vector<ll> potential(sz);
      vector<int> prev_v(sz,-1);
      vector<int> prev_e(sz,-1);
      priority_queue<pair<ll,int>> pq;
      pq.emplace(0,from);
      while(pq.size()){
        // auto [d, v] = pq.top();
        ll d, v;
        tie(d,v) = pq.top();
        d *= -1;
        pq.pop();
        if(dist[v] < d) continue;
        for(size_t i = 0; i < G[v].size(); ++i){
          const auto& e = G[v][i];
          if(e.cap == 0) continue;
          int v_ = e.to;
          ll d_ = d + e.cost + potential[v] - potential[v_];
          if(dist[v_] <= d_)
            continue;
          dist[v_] = d_;
          prev_v[v_] = v;
          prev_e[v_] = i;
          pq.emplace(-d_,e.to);
        }
      }
      if(dist[to] >= INF) return -1;
      for(int i = 0; i < sz; ++i)
        potential[i] += dist[i];
      int v = to;
      ll flow = f;
      while(v != from){
        int v_ = prev_v[v];
        flow = min(flow,G[v_][prev_e[v]].cap);
        v = v_;
      }
      v = to;
      while(v != from){
        int v_ = prev_v[v];
        auto& e = G[v_][prev_e[v]];
        e.cap -= flow;
        ans += flow*e.cost;
        G[v][e.r_idx].cap += flow;
        v = v_;
      }
      f -= flow;
    }
    return ans;
  }
};

int main(){
  int n, m, f;
  cin >> n >> m >> f;
  MinCostFlowGraph G(n);
  for(int i = 0; i < m; ++i){
    long long u, v, c, d;
    cin >> u >> v >> c >> d;
    G.add_edge(u,v,c,d);
  }
  cout << G.min_cost_flow(0,n-1,f) << endl;
}