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>
#define INF 1000000000
using namespace std;
typedef pair<int, int> pii;

class MinimumCostFlow {
	struct edge {
		int to, cap, cost, rev;
		edge(int to_, int cap_, int cost_, int rev_)
			: to(to_), cap(cap_), cost(cost_), rev(rev_) {}
	};
	int V;
	vector<vector<edge>> G;
	vector<int> h, dist, prevv, preve;
public:
	MinimumCostFlow(int _V) : V(_V), G(_V), h(_V), dist(_V), prevv(_V), preve(_V) {}
	void add(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 calc(int s, int t, int f) {
		int res = 0;
		fill(h.begin(), h.end(), 0);
		while (f > 0) {
			priority_queue<pii, vector<pii>, greater<pii>> que;
			fill(dist.begin(), dist.end(), 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 (size_t 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];
			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;
	MinimumCostFlow mcf(V);
	for (int i = 0, u, v, c, d; i < E; i++) {
		cin >> u >> v >> c >> d;
		mcf.add(u, v, c, d);
	}
	cout << mcf.calc(0, V - 1, F) << endl;
	return 0;
}