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 vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int W,H;
bool inrange(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define MP make_pair
struct Edge{
    int to,cap,cost,rev;
    Edge(int _to,int _cap,int _cost,int _rev){
        to=_to;
        cap=_cap;
        cost=_cost;
        rev=_rev;
    }
};
typedef vector<Edge> ve;
typedef vector<ve> vve;
class MCF{    //Minimum Cost Flow
    int inf = INF;
public:
    int n;
    vve G;
    vi h,dist,prev,pree;
    MCF(int size){
        n=size;
        G=vve(n);
        h=dist=prev=pree=vi(n);
    }
    void add_edge(int s,int t,int ca,int co){
        Edge e=Edge(t,ca,co,G[t].size());
        G[s].push_back(e);
        Edge ee=Edge(s,0,-co,G[s].size()-1);
        G[t].push_back(ee);
    }
    int mcf(int source,int sink,int f){
        int out=0;
        h=vi(n);
        while(f>0){
            priority_queue<pii,vector<pii> >q;
            dist=vi(n,inf);
            dist[source]=0;
            q.push(pii(0,source));
            while(!q.empty()){
                pii p=q.top();q.pop();
                int v=p.second;
                if(dist[v]<-p.first)continue;
                rep(i,G[v].size()){
                    Edge &e=G[v][i];
                    if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
                        dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                        prev[e.to]=v;
                        pree[e.to]=i;
                        q.push(pii(-dist[e.to],e.to));
                    }
                }
            }
            if(dist[sink]==inf)return -1;
            rep(i,n)h[i]+=dist[i];
            int d=f;
            for(int v=sink;v!=source;v=prev[v])d=min(d,G[prev[v]][pree[v]].cap);
            f-=d;
            out+=d*h[sink];
            for(int v=sink;v!=source;v=prev[v]){
                Edge &e=G[prev[v]][pree[v]];
                e.cap-=d;
                G[v][e.rev].cap+=d;
            }
        }
        return out;
    }
};

signed main(){
    int v,e,f; cin>>v>>e>>f;
    MCF hoge(v);
    rep(i,e){
        int a,b,c,d; cin>>a>>b>>c>>d;
        hoge.add_edge(a, b, c, d);
    }
    cout<<hoge.mcf(0, --v, f)<<endl;
}