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

//template<typename Int = int>
using Int = int;
struct PrimalDual {
    struct Edge {
        int dst;
        Int cap, flow, cost;
        int rev;
        bool isRev;
        Edge(int dst, Int cap, Int flow, Int cost, int rev, bool isRev)
            :dst(dst), cap(cap), flow(flow), cost(cost), rev(rev), isRev(isRev) {
        }
    };

    int n;
    vector<vector<Edge>> g;
    PrimalDual(int n_) : n(n_), g(vector<vector<Edge>>(n_)) {}
    void addEdge(int src, int dst, Int cap, Int cost) {
        g[src].emplace_back(dst, cap, 0, cost, g[dst].size(), false);
        g[dst].emplace_back(src, cap, cap, -cost, g[src].size() - 1, true);
    }

    vector<Int> h, dist;
    vector<int> prevv, preve;
    Int solve(int s, int t, Int f) {
        Int res = 0;
        h.assign(n, 0);
        dist.assign(n, 0);
        prevv.assign(n, 0);
        preve.assign(n, 0);
        while (f > 0) {
            if (!dijkstra(s,t)) return -1;
            for (int i = 0; i < n; ++i) h[i] += dist[i];
            Int d = f;
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = g[prevv[v]][preve[v]];
                d = min(d, residue(e));
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = g[prevv[v]][preve[v]];
                e.flow += d;
                g[v][e.rev].flow -= d;
            }
        }
        return res;
    }

    bool dijkstra(int s, int t) {
        constexpr Int INF = numeric_limits<Int>::max();
        dist.assign(n, INF);
        dist[s] = 0;
        priority_queue<pair<Int, int>> q;
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        q.emplace(0, s);
        while (q.size()) {
            int d, v;
            tie(d, v) = q.top();
            q.pop();
            d = -d;
            if (dist[v] < d) continue;
            for (int i = 0; i < (int)g[v].size(); ++i) {
                Edge &e = g[v][i];
                if (residue(e) > 0 && dist[e.dst] > dist[v] + e.cost + h[v] - h[e.dst]) {
                    dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst];
                    prevv[e.dst] = v;
                    preve[e.dst] = i;
                    q.emplace(-dist[e.dst], e.dst);
                }
            }
        }
        return dist[t] != INF;
    }

    Int residue(const Edge& e) { return e.cap - e.flow; }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, f;
    cin >> n >> m >> f;
    PrimalDual pd(n);
    for (int i = 0; i < m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        pd.addEdge(u, v, c, d);
    }
    cout << pd.solve(0, n - 1, f) << endl;
}