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;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)






#define MAX_V 100
struct edge { int to, cap, cost,rev; };

int V; // ????????°
vector<edge> G[MAX_V];
vector<int> h(MAX_V);	//??????????????£???
int dist[MAX_V];// ???????????¢
int prevv[MAX_V], preve[MAX_V];// ??´??????????????¨???

// from??????to??????????????????cap????????????cost????????????????????????????????????
void add_edge(int from, int to, int cap, int cost) {
	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});
}


int shortest_path(int s,vector<int> &d){
	int v = d.size();
	rep(i,d.size())d[i]=INF;
	d[s]=0;
	rep(loop,v){
		bool update = false;
		rep(i,MAX_V){
			for(auto e:G[i]){
				if(d[i]!=INF && d[e.to] > d[i]+e.cost){
					d[e.to] = d[i]+e.cost;
					update = true;
				}
			}
		}
		if(!update)break;
		if(loop==v-1)return true;	//negative_cycle
	}
	return false;
}


// s??????t????????????f???????°??????¨???????±???????
// ??????????????´??????-1?????????
int min_cost_flow(int s, int t, int f) {
	int res = 0;
	rep(i,h.size())h[i]=0;
	bool hoge=false;
	while (f > 0) {
		// ?????????????????????????????¨??????h?????´??°??????
		if(!f){
			shortest_path(s, h);
			f=true;
		}
		else{
			priority_queue<pii, vector<pii>, greater<pii> > que; fill(dist, dist + V, INF);
			dist[s] = 0;
			que.push(pii(0, s));
			while (!que.empty()) {
				pii p = que.top(); que.pop();
				int v = p.second;
				if (dist[v] < p.first) continue;
				for (int i = 0; i < G[v].size(); i++) {
					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]; prevv[e.to] = v;
						preve[e.to] = i;
						que.push(pii(dist[e.to], e.to));
					}
				}
			}
		}
		if (dist[t] == INF) return -1;	//????????\???????????????
		
		for (int v = 0; v < V; v++) h[v] += dist[v];
		
		// s-t????????????????????£??????????????????
		int 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]) {
			edge &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;
	rep(i,e){
		int u,v,c,d;
		cin>>u>>v>>c>>d;
		add_edge(u, v, c, d);
	}
	cout<<min_cost_flow(0, V-1, f)<<endl;
}