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 <queue>
#include <vector>

using namespace std;

constexpr int INF = 1000000001;
constexpr int MAX = 10000;

typedef pair<int, int> P;

struct Edge {
    int to;
    int cap;
    int cost;
    int rev;
    Edge(int to, int cap, int cost, int rev) 
        : to(to), cap(cap), cost(cost), rev(rev) {}
};

int V, E, F;
vector<Edge> G[MAX];
int h[MAX];
int dist[MAX];
int prevv[MAX], preve[MAX];

auto add_edge(int from, int to, int cap, int cost) -> void {
    G[from].push_back(Edge(to, cap, cost, G[to].size()));
    G[to].push_back(Edge(from, 0, -cost, G[from].size() - 1));
}

auto min_cost_flow(int s, int t, int f) -> int {
    auto res = 0;
    fill(h, h + V, 0);
    while(f > 0) {
        priority_queue<P, vector<P>, greater<P>> que;
        fill(dist, dist + V, INF);
        dist[s] = 0;
        que.push(P(0, s));
        while(!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (dist[v] < p.first) continue;
            for (auto i = 0; i < G[v].size(); i++) {
                Edge &e = G[v][i];
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.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 (auto v = t; v != s; v = prevv[v]) {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * h[t];
        for (auto 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;
}

auto main(int argc, char const *argv[]) -> int {
    int n;

    cin>>V>>E>>F;
    while(E--){
        int u, v, c, d;
        cin>>u>>v>>c>>d;
        add_edge(u,v,c,d);
    }

    cout<<min_cost_flow(0, V - 1, F)<<endl;

    return 0;
}