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:
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <random>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define rep(i,n)	for(int i=0;i<n;i++)
#define srep(i,a,n)	for(int i=a;i<n;i++)
#define REP(i,n)	for(int i=0;i<=n;i++)
#define SREP(i,a,n)	for(int i=a;i<=n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
#define fst	first
#define scn second
#define bicnt(x)	__buildin__popcount(x)
#define gcd(a,b)	__gcd__(a,b)
#define debug(x)	cout<<"debug: "<<x<<endl
#define DEBUG 0
const ll inf = (ll)1e9;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

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 n;
vector<edge> e[1010];
int h[1010];
int dist[1010];
int prevv[1010], preve[1010];

void add_edge(int s, int t, int cap, int cost) {
	e[s].push_back(edge(t, cap, cost, e[t].size()));
	e[t].push_back(edge(s, 0, -cost, e[s].size() - 1));
}

int min_cost_flow(int s, int t, int f) {
	int ret = 0;
	REP(i, n)	h[i] = 0;
	while (f > 0) {
		priority_queue<pii> pq;
		pq.push(mp(0, -s));
		REP(i, n)	dist[i] = inf;
		dist[s] = 0;
		while (!pq.empty()) {
			auto it = pq.top();	pq.pop();
			int v = -it.second, cost = -it.first;
			if (dist[v] < cost)	continue;
			rep(i, e[v].size()) {
				edge* to = &e[v][i];
				if (to->cap > 0 && dist[to->to] > dist[v] + to->cost + h[v] - h[to->to]) {
					dist[to->to] = dist[v] + to->cost + h[v] - h[to->to];
					prevv[to->to] = v;
					preve[to->to] = i;
					pq.push(mp(-dist[to->to], -to->to));
				}
			}
		}
		if (dist[t] == inf)	return -1;
		rep(i, n)	h[i] += dist[i];
		int d = f;
		for (int i = t; i != s; i = prevv[i]) {
			d = min(d, e[prevv[i]][preve[i]].cap);
		}
		f -= d;
		ret += d*h[t];
		for (int i = t; i != s; i = prevv[i]) {
			edge* to = &e[prevv[i]][preve[i]];
			to->cap -= d;
			e[i][to->rev].cap += d;
		}
	}
	return ret;
}

int main() {
	int e, f;	cin >> n >> e >> f;
	rep(i, e) {
		int s, t, c, d;	cin >> s >> t >> c >> d;
		add_edge(s, t, c, d);
	}
	cout << min_cost_flow(0, n - 1, f) << endl;
	return 0;
}