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>
#define fi first
#define se second
typedef long long ll;
using namespace std;

//BEGIN CUT HERE
//Min_cost_flow
class Min_cost_flow{
public:
    explicit Min_cost_flow(int n):vertex(static_cast<unsigned int>(n+10)){
        G.resize(vertex);
        prev_e.resize(vertex);
        prev_v.resize(vertex);
    }

    void add_edge(int from,int to,ll cap,ll cost){
        G[from].push_back((edge){to, cap, cost, static_cast<int>(G[to].size())});
        G[to].push_back((edge){from, 0, -cost, static_cast<int>(G[from].size() - 1)});
    }

    ll flow(int s,int t,ll f){
        ll res=0;
        h.clear();
        h.resize(vertex,0);
        while(f>0){
            vector<ll> dist;
            dist.resize(vertex);
            dist=dijkstra(s);
            if(dist[t]==INF)return -1;
            for(int i=0;i<vertex;i++)h[i]+=dist[i];
            ll d=f;
            for(int i=t;i!=s;i=prev_v[i]){
                d=min(d,G[prev_v[i]][prev_e[i]].cap);
            }
            f-=d;
            res+=d*h[t];
            for(int i=t;i!=s;i=prev_v[i]){
                edge &e=G[prev_v[i]][prev_e[i]];
                e.cap-=d;
                G[i][e.rev].cap+=d;
            }
        }
        return res;
    }
private:
    struct edge{
        int to;
        ll cap;
        ll cost;
        int rev;
    };

    unsigned int vertex;
    ll INF=(ll)1e16;
    vector<vector<edge> > G;
    vector<ll> h;
    vector<int> prev_v,prev_e;

    vector<ll> dijkstra(int start){
        vector<ll> dist(vertex,INF);
        dist[start]=0;
        priority_queue<pair<ll,int> > q;
        q.push({0,start});
        while(!q.empty()){
            int now=q.top().se;
            ll now_cost=-q.top().fi;
            q.pop();
            if(now_cost>dist[now])continue;
            for(int i=0;i<(int)G[now].size();i++){
                edge &e=G[now][i];
                if(e.cap>0 && dist[e.to]>dist[now]+e.cost+h[now]-h[e.to]){
                    dist[e.to]=dist[now]+e.cost+h[now]-h[e.to];
                    prev_v[e.to]=now;
                    prev_e[e.to]=i;
                    q.push({-dist[e.to],e.to});
                }
            }
        }
        return dist;
    }
};


int main(){
    int v,e,f;cin>>v>>e>>f;
    Min_cost_flow m(v);
    for(int i=0;i<e;i++){
        int from,to,cap,cost;
        cin>>from>>to>>cap>>cost;
        m.add_edge(from,to,cap,cost);
    }
    cout<<m.flow(0,v-1,f)<<endl;
}