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;
typedef long long ll;
#define rep(i,n) for (ll i=0;i<(n);++i)
const ll MOD=1e9+7;

template<typename T,typename E>
struct PrimalDual{
    const E inf=numeric_limits<E>::max()/2;
    struct edge{
        int to,rev; T cap; E cost;
        edge(int to,T cap,E cost,int rev):
            to(to),cap(cap),cost(cost),rev(rev){}
    };
    vector<vector<edge>> G;
    vector<E> h,dist;
    vector<int> prevv,preve;
    PrimalDual(int n):G(n),h(n),dist(n),prevv(n),preve(n){}
    void add_edge(int from,int to,T cap,E cost){
        G[from].emplace_back(to,cap,cost,G[to].size());
        G[to].emplace_back(from,0,-cost,G[from].size()-1);
    }
    void dijkstra(int s){
        struct P{
            E first; int second;
            P(E first,int second):first(first),second(second){}
            bool operator<(const P &a) const{
                return a.first<first;
            }
        };
        priority_queue<P> pq;
        fill(dist.begin(),dist.end(),inf);
        dist[s]=0;
        pq.emplace(dist[s],s);
        while(!pq.empty()){
            P p=pq.top(); pq.pop();
            int v=p.second;
            if (dist[v]<p.first) continue;
            for (int i=0;i<G[v].size();++i){
                edge &e=G[v][i];
                if (e.cap>0&&dist[v]+e.cost+h[v]-h[e.to]<dist[e.to]){
                    dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                    prevv[e.to]=v,preve[e.to]=i;
                    pq.emplace(dist[e.to],e.to);
                }
            }
        }
    }
    E min_cost_flow(int s,int t,T f){
        E res=0;
        fill(h.begin(),h.end(),0);
        while(f>0){
            dijkstra(s);
            if (dist[t]==inf) return -1;
            for (int v=0;v<h.size();++v){
                if (dist[v]<inf) h[v]+=dist[v];
            }
            T d=f;
            for (int v=t;v!=s;v=prevv[v]){
                d=min(d,G[prevv[v]][preve[v]].cap);
            }
            f-=d;
            res+=h[t]*d;
            for (int 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;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int V,E,F; cin >> V >> E >> F;
    PrimalDual<int,int> PD(V);
    rep(i,E){
        int u,v,c,d; cin >> u >> v >> c >> d;
        PD.add_edge(u,v,c,d);
    }
    cout << PD.min_cost_flow(0,V-1,F) << endl;
}