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;
#define INF 1e9
struct edge{
	//行先、容量、コスト、逆辺
	int to,cap,cost,rev;	
};	
void add_edge(int from,int to,int cap ,int cost,vector<vector<edge> > &g){
	g[from].push_back( (edge) { to,cap,cost,(int)g[to].size() } );
	g[to].push_back( (edge){from,0, -cost,(int)g[from].size()-1});
}
// s to t minmun flow 
// can't reach -1
int min_cost_flow(int s,int t,int f,vector<vector<edge> > &g){
	int res = 0;
	int v = (int)g.size();
	vector<int> prevv(v),preve(v);
	while( f > 0 ){
		//bellmanford s-t周辺最短路を求める
		vector<int> dist(v,INF);
		dist[s] = 0;
		bool update = true;
		while(update){
			update = false;
			for(int j= 0;j<v;j++){
				if(dist[j] == INF) continue;
				for(int i= 0;i<g[j].size();i++){
					edge &e = g[j][i];
					if(e.cap > 0 && dist[e.to] > dist[j] + e.cost){
						dist[e.to] = dist[j]  + e.cost;
						prevv[e.to] = j;
						preve[e.to] = i;
						update = true;
					}
				}
			}
		}
		if(dist[t] == INF ) return -1; //can't reach 
		//s-t周辺に目いっぱい流す
		int d = f;
		for(int i = t; i!= s; i = prevv[i]) d = min(d,g[prevv[i]][preve[i]].cap);
		f -= d;
		res += d*dist[t];
		for(int i = t; i!= s; i = prevv[i]){
			edge &e = g[prevv[i]][preve[i]];
			e.cap  -= d;
			g[i][e.rev].cap  += d;
		}
	}
	return res;
}


int main(){
	int v,e,f;
	cin>>v>>e>>f;
	vector<vector<edge> > g(v);
	for(int i=0;i<e;i++){
	int c,d,u,v;
	cin>>u>>v>>c>>d;
	add_edge(u,v,c,d,g);
	}
	cout<<min_cost_flow(0,v-1,f,g)<<endl;
	return 0;
}