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 <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

template <typename T>
class MinCostFlow
{
public:
  MinCostFlow(int n) : n(n), capacity(n, vector<T>(n)), cost(n, vector<T>(n)), prev(n) {}

  void add_edge(int src, int dst, T cap, T c)
  {
    capacity[src][dst] = cap;
    capacity[dst][src] = 0;
    cost[src][dst] = c;
    cost[dst][src] = -c;
  }

  T min_cost_flow(int s, int t, T f)
  {
    T res = 0;
    h.assign(n, 0);
    while (f > 0)
    {
      if (!dijkstra(s, t))
        return -1;
      for (int i = 0; i < n; ++i)
        h[i] += dist[i];

      T d = f;
      for (int v = t; v != s; v = prev[v])
        d = min(d, capacity[prev[v]][v]);
      f -= d;
      res += d * h[t];
      for (int v = t; v != s; v = prev[v])
      {
        capacity[prev[v]][v] -= d;
        capacity[v][prev[v]] += d;
      }
    }
    return res;
  }

private:
  int n;
  T inf = numeric_limits<T>::max();
  vector<vector<T>> capacity, cost;
  vector<T> dist, h, prev;

  bool dijkstra(int s, int t)
  {
    dist.assign(n, inf);
    dist[s] = 0;
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
    pq.emplace(0, s);
    while (!pq.empty())
    {
      int c = pq.top().first;
      int v = pq.top().second;
      pq.pop();
      if (dist[v] < c)
        continue;
      for (int nv = 0; nv < n; ++nv)
      {
        if (capacity[v][nv] > 0 && dist[nv] > dist[v] + cost[v][nv] + h[v] - h[nv])
        {
          dist[nv] = dist[v] + cost[v][nv] + h[v] - h[nv];
          prev[nv] = v;
          pq.emplace(dist[nv], nv);
        }
      }
    }
    return dist[t] != inf;
  }
};

int main()
{
  int V, E, F, u, v, c, d;
  cin >> V >> E >> F;
  MinCostFlow<int> mcf(V + 1);
  for (int i = 0; i < E; ++i)
  {
    cin >> u >> v >> c >> d;
    mcf.add_edge(u, v, c, d);
  }
  cout << mcf.min_cost_flow(0, V - 1, F) << endl;
  return 0;
}