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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

/* Minimum Cost Flow */

struct MinimumCostFlow{

  typedef pair<int,int> P;
  
  struct edge {
    int to, cap, cost, rev;
    edge(int a, int b, int c, int d):to(a),cap(b),cost(c),rev(d){}
  };
  
  vector<vector<edge> > G;
  vector<int> h, dist, prevv, preve;
  int V;
  
  MinimumCostFlow(int v):G(v,vector<edge>()),prevv(v,0),preve(v,0),V(v){}
  
  int add_edge(int from,int to,int cap, int cost){
    int id = G[from].size();
    
    G[from].push_back(edge(to,cap,cost,G[to].size()));
    G[to].push_back(edge(from,0,-cost,G[from].size() - 1));
    
    return id;
  }

  int solve(int s, int t, int f){
    int res = 0;
    h.assign(V,0);
    while(f > 0){
      priority_queue<P, vector<P>, greater<P> > pq;
      dist.assign(V, INF);
      dist[s] = 0;
      pq.push(P(0, s));
      while(pq.size()){
        P p = pq.top(); pq.pop();
        int v = p.second;
        if(dist[v] < p.first) continue;

        for(int i = 0; i < G[v].size(); i++){
          edge &e = G[v][i];
          int d = dist[v] + e.cost + h[v] - h[e.to];
          if(e.cap > 0 && dist[e.to] > d){
            dist[e.to] = d;
            prevv[e.to] = v;
            preve[e.to] = i;
            pq.push(P(dist[e.to], e.to));
          }
        }
      }
      if(dist[t] == INF) return -1;

      for(int v = 0; v < V; v++) h[v] += dist[v];

      int d = f;
      for(int v = t; v != s; v = prevv[v])
        d = min(d, G[prevv[v]][preve[v]].cap);

      f -= d;
      res += d * h[t];

      for(int v = t; v != s; v = prevv[v]){
        edge &e = G[prevv[v]][preve[v]];
        e.cap -= d;
        G[v][e.rev].cap += d;
      }
    }

    return res;
  }

};


int main(){
  int v,e,f;
  int a,b,c,d;
  
  scanf("%d%d%d",&v,&e,&f);

  MinimumCostFlow flow(v);
  
  for(int i=0;i<e;i++){
    scanf("%d%d%d%d",&a,&b,&c,&d);

    flow.add_edge(a,b,c,d);
  }

  cout << flow.solve(0, v-1, f) << endl;
  
  return 0;
}