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 <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Network{
	private:
	int V;
	struct edge{
		int to,cap,cost,rev;
	};
	vector<vector<edge> > g;
	vi h,d,pv,pe;
	public:
	Network(int v){
		V=v;
		g=vector<vector<edge> >(v);
	}
	void add_edge(int s,int t,int cap,int cost){
		g[s].push_back(edge{t,cap,cost,(int)g[t].size()});
		g[t].push_back(edge{s,0,-cost,(int)g[s].size()-1});
	}
	int min_cost_flow(int s,int t,int f){
		int res=0;
		h=pv=pe=vi(V);
		while(f>0){
			priority_queue<P> q;
			d=vi(V,inf);
			d[s]=0;
			q.push({0,s});
			while(!q.empty()){
				P p=q.top();
				q.pop();
				int v=p.second;
				if(d[v]<-p.first) continue;
				for(int i=0;i<g[v].size();i++){
					edge &e=g[v][i];
					if(e.cap>0&&d[e.to]>d[v]+e.cost+h[v]-h[e.to]){
						d[e.to]=d[v]+e.cost+h[v]-h[e.to];
						pv[e.to]=v;
						pe[e.to]=i;
						q.push({-d[e.to],e.to});
					}
				}
			}
			if(d[t]==inf) return -1;
			for(int i=0;i<V;i++) h[i]+=d[i];
			int D=f;
			for(int i=t;i!=s;i=pv[i]) D=min(D,g[pv[i]][pe[i]].cap);
			f-=D;
			res+=D*h[t];
			for(int i=t;i!=s;i=pv[i]){
				edge &e=g[pv[i]][pe[i]];
				e.cap-=D;
				g[i][e.rev].cap+=D;
			}
		}
		return res;
	}
};

int n,m,f;

int main(){
	cin>>n>>m>>f;
	Network net(n);
	for(int i=0;i<m;i++){
		int v,u,c,d;
		cin>>v>>u>>c>>d;
		net.add_edge(v,u,c,d);
	}
	cout<<net.min_cost_flow(0,n-1,f)<<endl;
}