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 <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

// BEGIN CUT HERE
template<class T> struct PrimalDual {
  struct Edge { int to, rev; T cap, cost; };
  const T inf = numeric_limits<T>::max();
  const int n;
  VV<Edge> g;
  V<T> pot, dist;
  V<> pv, pe;
  PrimalDual(int n) : n(n), g(n), pot(n), dist(n), pv(n), pe(n) {}
  void add_edge(int from, int to, T cap, T cost) {
    assert(from != to);
    assert(cap >= 0);
    if (!cap) return;
    assert(cost >= 0);
    g[from].emplace_back(Edge{to, (int) g[to].size(), cap, cost});
    g[to].emplace_back(Edge{from, (int) g[from].size() - 1, 0, -cost});
  }
  void dijkstra(int s) {
    using P = pair<T, int>;
    priority_queue< P, V<P>, greater<P> > pque;
    fill(begin(dist), end(dist), inf);
    pque.emplace(dist[s] = 0, s);
    while (!pque.empty()) {
      T d; int v;
      tie(d, v) = pque.top(); pque.pop();
      if (d > dist[v]) continue;
      for (int i = 0; i < (int) g[v].size(); ++i) {
        const Edge& e = g[v][i];
        if (!e.cap or dist[e.to] <= dist[v] + e.cost - (pot[e.to] - pot[v])) continue;
        pv[e.to] = v, pe[e.to] = i;
        pque.emplace(dist[e.to] = dist[v] + e.cost - (pot[e.to] - pot[v]), e.to);
      }
    }
  }
  T min_cost_flow(int s, int t, T f) {
    assert(s != t);
    assert(f >= 0);
    T res = 0;
    fill(begin(pot), end(pot), 0);
    while (f > 0) {
      dijkstra(s);
      if (dist[t] == inf) return -1;
      for (int v = 0; v < n; ++v) pot[v] += dist[v];
      T d = f;
      for (int v = t; v != s; v = pv[v]) {
        d = min(d, g[pv[v]][pe[v]].cap);
      }
      f -= d;
      res += d * pot[t];
      for (int v = t; v != s; v = pv[v]) {
        Edge& e = g[pv[v]][pe[v]];
        e.cap -= d;
        g[v][e.rev].cap += d;
      }
    }
    return res;
  }
};
// END CUT HERE

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m, f; cin >> n >> m >> f;
  PrimalDual<int> g(n);
  while (m--) {
    int 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) << '\n';
}