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;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

// ????°??????¨??? O(F |E| |V|)
struct MinCostFlow
{
    typedef pair<int, int> P;   // first -> minDist, second -> v
    struct Edge
    {
        int to, cap, cost, rev;
    };
    const int V;
    vector<vector<Edge>> G;
    vector<int> dist, prevv, preve;
    MinCostFlow(int v) : V(v), G(v), dist(v), prevv(v), preve(v){}
    void add_edge(int from, int to, int cap, int cost) {
        G[from].push_back({to, cap, cost, (int)G[to].size()});
        G[to].push_back({from, 0, -cost, (int)G[from].size()-1});
    }
    // minCostFlow s -> t
    // noexist flow return -1
    int min_cost_flow(int s, int t, int f) {
        int res = 0;
        while(f > 0) {
            for(int i = 0; i < V; ++i) dist[i] = INF;
            dist[s] = 0;
            bool update = true;
            while(update) {
                update = false;
                for(int v = 0; v < V; ++v) {
                    if(dist[v] == INF) continue;
                    for(int i = 0; i < G[v].size(); ++i) {
                        Edge& e = G[v][i];
                        if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                            dist[e.to] = dist[v] + e.cost;
                            prevv[e.to] = v;
                            preve[e.to] = i;
                            update = true;
                        }
                    }
                }
            }
            if(dist[t] == INF) return -1;
            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 * dist[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;
    cin >> V >> E >> F;
    MinCostFlow f(V);
    rep(i, E) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        f.add_edge(a, b, c, d);
    }
    cout << f.min_cost_flow(0, V-1, F) << endl;
    return 0;
}