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 fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define fth(t) std::get<3>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;


const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

int V, E, F;
// to, rev, cap, cost
std::vector<std::tuple<int, int, int, int>> G[200];

void addEdge(int u, int v, int cap, int cost){
    G[u].emplace_back(v, G[v].size(), cap, cost);
    G[v].emplace_back(u, G[u].size() - 1, 0, -cost);
}

int dist[1500];
tuple<int, int, int> prevs[1500];
const int INF = numeric_limits<int>::max() / 2;

void bellmanFord(int s){
    std::fill(dist, dist+V, INF);
    std::fill(prevs, prevs+V, std::make_tuple(-1, -1, -1));
    dist[s] = 0;

    for(int i=0;i<V;++i){
        bool updated = false;
        
        for(int u=0;u<V;++u){
            for(int k=0;k<G[u].size();++k){
                const auto& p = G[u][k];
                int v, rev, cap, c;
                std::tie(v, rev, cap, c) = p;
                if(cap <= 0){continue;}
                if(dist[v] > dist[u] + c){
                    updated = true;
                    dist[v] = dist[u] + c;
                    prevs[v] = std::make_tuple(u, k, rev);
                }
            }            
        }

        if(!updated){break;}
    }
}

int f(){
    ll res = 0;
    
    while(F > 0){
        bellmanFord(0);

        if(dist[V-1] == INF){
            return -1;
        }
        
        int v = V - 1;
        int d = F;
        while(v != 0){
            int pv, e_idx;
            tie(pv, e_idx, ignore) = prevs[v];

            d = min(d, thd(G[pv][e_idx]));
            
            v = pv;
        }

        F -= d;
        res += 1ll * d * dist[V-1];

        v = V - 1;
        while(v != 0){
            int pv, e_idx, rev;
            tie(pv, e_idx, rev) = prevs[v];

            thd(G[pv][e_idx]) -= d;
            thd(G[v][rev]) += d;
            
            v = pv;
        }        
    }

    return res;
}

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::cin >> V >> E >> F;

    for(int i=0;i<E;++i){
        int u, v, c, d;
        std::cin >> u >> v >> c >> d;

        addEdge(u, v, c, d);
    }

    ll res = f();
    std::cout << res << std::endl;
}