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;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int MAX_V=110;
struct edge{int to;ll cap;ll cost;int rev;};
int tmp1,tmp2;

int V;//頂点数
vector<vector<edge>> g(MAX_V);
vll h(MAX_V);//ポテンシャル
vll dist(MAX_V);
vin prevv(MAX_V),preve(MAX_V);//直前の頂点と辺

void add_edge(int from,int to,ll cap,ll cost){
    tmp1=g[to].size();tmp2=g[from].size();
    g[from].push_back((edge){to,cap,cost,tmp1});
    g[to].push_back((edge){from,(ll)0,-cost,tmp2});
}

//sからtへの最小費用流を求める
//ながせない場合は-1
ll min_cost_flow(int s,int t,ll f){
    ll res=(ll)0;
    fill(all(h),(ll)0);
    ll d;
    while(f>0){
        //dijkstraを用いてhを初期化
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        fill(all(dist),(ll)inf);
        dist[s]=(ll)0;
        pq.push(mp((ll)0,s));
        while(pq.size()){
            auto p=pq.top();pq.pop();
            int v=p.second;
            if(dist[v]<p.first)continue;
            for(int i=0;i<g[v].size();i++){
                auto& 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];
                    prevv[e.to]=v;
                    preve[e.to]=i;
                    pq.push(mp(dist[e.to],e.to));
                }
            }
        }
        if(dist[t]==inf)return -1;
        rep(v,V)h[v]+=dist[v];
        d=f;
        for(int v=t;v!=s;v=prevv[v])d=min(d,g[prevv[v]][preve[v]].cap);
        f-=d;
        res+=d*h[t];
        for(int v=t;v!=s;v=prevv[v]){
            auto& e=g[prevv[v]][preve[v]];
            e.cap-=d;
            g[v][e.rev].cap+=d;
        }
    }
    return res;
}

int main(){
    int e,f;cin>>V>>e>>f;
    int u,v;ll c,d;
    rep(i,e){
        cin>>u>>v>>c>>d;
        add_edge(u,v,c,d);
    }
    cout<<min_cost_flow(0,V-1,f)<<endl;
}