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> >;


template<class T> struct PrimalDual {
  struct Edge {
    int to, rev;
    T cap, cost;
  };
  const int n;
  const T inf = numeric_limits<T>::max();
  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);
    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 < g[v].size(); ++i) {
        const Edge& e = g[v][i];
        if (e.cap <= 0 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;
  }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m, f; cin >> n >> m >> f;
  PrimalDual<int> pd(n);
  for (int i = 0; i < m; ++i) {
    int from, to, cap, cost; cin >> from >> to >> cap >> cost;
    pd.add_edge(from, to, cap, cost);
  }
  cout << pd.min_cost_flow(0, n - 1, f) << '\n';
}