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

namespace Flow {
    struct Edge {
        int to, capacity, cost, reverse;
        Edge(int to, int capacity, int cost, int reverse) :
            to(to), capacity(capacity), cost(cost), reverse(reverse) {}
    };
    template <int MaxN> class PrimalDual {
        int n = MaxN;
        vector<Edge> g[MaxN];
    public:
        void clear(int n) {
            this->n = n;
            for (int i = 0; i < n; ++i)
                g[i].clear();
        }
        void push(int from, int to, int capacity = 1, int cost = 0) {
            g[from].emplace_back(to, capacity, cost, g[to].size());
            g[to].emplace_back(from, 0, -cost, g[from].size() - 1);
        }
        pair<int, int> flow(int s, int t, int f = 1 << 30) {
            int flow = f, cost = 0;
            static int prevv[MaxN], preve[MaxN], dist[MaxN], h[MaxN];
            fill(h, h + n, 0);
            while (flow > 0) {
                fill(dist, dist + n, 1 << 30);
                dist[s] = 0;
                using P = pair<int, int>;
                priority_queue<P, vector<P>, greater<P>> q;
                for (q.emplace(0, s); q.size(); ) {
                    auto p = q.top();
                    q.pop();
                    int v = p.second;
                    if (dist[v] < p.first) continue;
                    for (auto& e : g[v]) {
                        int d = dist[v] + e.cost + h[v] - h[e.to];
                        if (e.capacity > 0 && dist[e.to] > d) {
                            dist[e.to] = d;
                            prevv[e.to] = v;
                            preve[e.to] = &e - &g[v][0];
                            q.emplace(d, e.to);
                        }
                    }
                }
                if (dist[t] == 1 << 30) break;
                for (int v = 0; v < n; ++v)
                    h[v] += dist[v];
                int d = flow;
                for (int v = t; v != s; v = prevv[v])
                    d = min(d, g[prevv[v]][preve[v]].capacity);
                flow -= d;
                cost += d * h[t];
                for (int v = t; v != s; v = prevv[v]) {
                    auto& e = g[prevv[v]][preve[v]];
                    e.capacity -= d;
                    g[v][e.reverse].capacity += d;
                }
            }
            return { f - flow, cost };
        }
    };
}

int main() {
    int n, m, f;
    cin >> n >> m >> f;
    Flow::PrimalDual<100> pd;
    pd.clear(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        pd.push(a, b, c, d);
    }
    auto p = pd.flow(0, n - 1, f);
    cout << (p.first == f ? p.second : -1) << endl;
    return 0;
}