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>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;


const int MAX_V = 101;

class Edge{
    public:
        //???????????????????????????????????????
        int to, cap, cost, rev;
};

vector<vector<Edge>> G(MAX_V);
int h[MAX_V]; //??????????????£???
int dist[MAX_V]; //???????????¢
int prev_v[MAX_V], prev_e[MAX_V]; //??´??????????????¨???

void addEdge(int from, int to, int cap, int cost){
    G[from].emplace_back(Edge{to, cap, cost, static_cast<int>(G[to].size())});
    G[to].emplace_back(Edge{from, 0, -cost, static_cast<int>(G[from].size() - 1)});
}

int minCostFlow(int v, int s, int t, int f){
    int res = 0;
    fill(h, h + v, 0);
    while(f > 0){
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        fill(dist, dist + v, INF);
        dist[s] = 0;
        q.push(make_pair(0, s));
        while(not q.empty()){
            pair<int, int> p = q.top(); q.pop();
            int u = p.second;
            if(dist[u] < p.first) continue;
            rep(i,G[u].size()){
                Edge &e = G[u][i];
                if(e.cap > 0 && dist[e.to] > dist[u] + e.cost + h[u] - h[e.to]){
                    dist[e.to] = dist[u] + e.cost + h[u] - h[e.to];
                    prev_v[e.to] = u;
                    prev_e[e.to] = i;
                    q.push(make_pair(dist[e.to], e.to));
                }
            }
        }
        if(dist[t] == INF){
            return -1;
        }
        rep(i,v) h[i] += dist[i];

        int d = f;
        for(int u = t; u != s; u = prev_v[u]){
            d = min(d, G[prev_v[u]][prev_e[u]].cap);
        }
        f -= d;
        res += d * h[t];
        for(int u = t; u != s; u = prev_v[u]){
            Edge &e = G[prev_v[u]][prev_e[u]];
            e.cap -= d;
            G[u][e.rev].cap += d;
        }
    }
    return res;
}

int main(){
    int v, e, f;
    cin >> v >> e >> f;
    rep(i,e){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        addEdge(a,b,c,d);
    }
    cout << minCostFlow(v, 0, v - 1, f) << endl;
}