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:
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B&lang=jp

#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int>P;

class MCF{
public:
	class edge{
	public:
		int to, cap, cost, rev;
		edge(){};
		edge(int _to, int _cap, int _cost, int _rev){
			to = _to;
			cap = _cap;
			cost = _cost;
			rev = _rev;
		}
	};

	vector<vector<edge> >G;
	vector<int>h;
	vector<int>dist;
	vector<int>prevv;
	vector<int>preve;
	MCF(int n){
		G.resize(n);
		preve.resize(n, 0);
		prevv.resize(n, 0);
	}
	void addEdge(int from, int to, int cap, int cost){
		G[from].push_back(edge(to, cap, cost, G[to].size()));
		G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
	}
	int flow(int s, int t, int f){
		int res = 0;
		h.clear();
		h.resize(G.size(), 0);
		while (f > 0){
			priority_queue<P, vector<P>, greater<P> >que;
			dist.clear();
			dist.resize(G.size(), 1145141919);
			dist[s] = 0;
			que.push(P(0, s));
			while (!que.empty()){
				P 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(P(dist[e.to], e.to));
					}
				}
			}
			if (dist[t] == 1145141919){
				return -1;
			}
			for (int v = 0; v < G.size(); v++)h[v] += dist[v];
			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 V, E, F;
	cin >> V >> E >> F;
	MCF mcf(V);
	for (int i = 0; i < E; i++){
		int from, to, cap, cost;
		cin >> from >> to >> cap >> cost;
		mcf.addEdge(from, to, cap, cost);
	}
	cout << mcf.flow(0, V - 1, F) << endl;

	return 0;
}