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:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
template <typename Flow, typename Cost> class PrimalDual {
private:
  Cost INF_COST = std::numeric_limits<Cost>::max();
public:
  struct Edge {
    int to;
    Flow cap;
    Cost cost;
    int rev;
    Edge () {}
    Edge (int t, Flow f, Cost c, int rev) : to(t), cap(f), cost(c), rev(rev) {}
  };
private:
  vector<vector<Edge>> graph;
  vector<Cost> potential, min_cost;
  vector<int> prev_v, prev_e;

public:
  PrimalDual (int n) : graph(n) {}

  void add (int from, int to, Flow cap, Cost cost) {
    graph[from].push_back(Edge(to, cap, cost, (int) graph[to].size()));
    graph[to].push_back(Edge(from, 0, -cost, (int) graph[from].size() - 1));
  }

  Cost get (int start, int goal, Flow f) {
    int n = (int) graph.size();
    Cost res = 0;
    using Pi = pair<Cost, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    potential.assign(n, 0);
    prev_e.assign(n, -1);
    prev_v.assign(n, -1);

    while (f > 0) {
      min_cost.assign(n, INF_COST);
      que.emplace(0, start);
      min_cost[start] = 0;
      while (que.size()) {
        Pi cur = que.top();
        que.pop();
        if (min_cost[cur.second] < cur.first) continue;
        for (int i = 0; i < (int) graph[cur.second].size(); i++) {
          Edge& e = graph[cur.second][i];
          Cost next_cost = min_cost[cur.second] + e.cost + potential[cur.second] - potential[e.to];
          if (e.cap > 0 && min_cost[e.to] > next_cost) {
            min_cost[e.to] = next_cost;
            prev_v[e.to] = cur.second;
            prev_e[e.to] = i;
            que.emplace(min_cost[e.to], e.to);
          }
        }
      }
    
      if (min_cost[goal] == INF_COST) return -1;
      for (int i = 0; i < n; i++) potential[i] += min_cost[i];
      Flow add_flow = f;
      for (int i = goal; i != start; i = prev_v[i]) {
        add_flow = min(add_flow, graph[prev_v[i]][prev_e[i]].cap);
      }
      f -= add_flow;
      res += add_flow * potential[goal];
      for (int i = goal; i != start; i = prev_v[i]) {
        Edge& e = graph[prev_v[i]][prev_e[i]];
        e.cap -= add_flow;
        graph[i][e.rev].cap += add_flow;
      }
    }
    return res;
  }
};
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m, f;
  cin >> n >> m >> f;
  PrimalDual<int, int> pd(n);
  for (int i = 0; i < m; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    pd.add(a, b, c, d);
  }
  cout << pd.get(0, n - 1, f) << '\n';
  return 0;
}