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;

template <typename Cap, typename Cost>
struct Graph {
  const Cost INF = numeric_limits<Cost>::max();
  struct Edge {
    int to, rev;
    Cap cap;
    Cost cost;
    Edge(int to, Cap cap, Cost cost, int rev)
      : to(to), cap(cap), cost(cost), rev(rev) {}
  };
  vector<vector<Edge>> g;
  int n;
  Graph(int n) : n(n) {
    g.assign(n, vector<Edge>());
  }
  void add_edge(int v, int u, Cap cap = 1, Cost cost = 0) {
    g[v].emplace_back(u, cap, cost, (int) g[u].size());
    g[u].emplace_back(v, 0, -cost, (int) g[v].size() - 1);
  }
  vector<Edge>& operator[](int x) {
    return g[x];
  }
  Cost min_cost_flow(int s, int t, Cap f) {
    Cost ret = 0;
    while (f > 0) {
      vector<Cost> dist(n, INF);
      vector<int> prevv(n), preve(n);
      dist[s] = 0;
      while (true) {
        bool update = false;
        for (int v = 0; v < n; v++) {
          for (int i = 0; i < g[v].size(); i++) {
            auto &e = g[v][i];
            if (e.cap == 0) continue;
            if (dist[v] == INF || dist[e.to] <= dist[v] + e.cost) continue;
            dist[e.to] = dist[v] + e.cost;
            prevv[e.to] = v, preve[e.to] = i;
            update = true;
          }
        }
        if (!update) break;
      }
      if (dist[t] == INF) return INF;
      Cap cap = f;
      for (int v = t; v != s; v = prevv[v]) {
        cap = min(cap, g[prevv[v]][preve[v]].cap);
      }
      f -= cap;
      ret += cap * dist[t];
      for (int v = t; v != s; v = prevv[v]) {
        auto &e = g[prevv[v]][preve[v]];
        e.cap -= cap;
        g[v][e.rev].cap += cap;
      }
    }
    return ret;
  }
};

int main() {
  int n, m, f;
  cin >> n >> m >> f;
  Graph<int, int> g(n);
  for (int i = 0; i < m; i++) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    g.add_edge(u, v, c, d);
  }
  int ans = g.min_cost_flow(0, n - 1, f);
  if (ans == g.INF) {
    ans = -1;
  }
  cout << ans << endl;
  return 0;
}