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:
//最短経路長が短い経路に流せるだけ流す。
//ただし、順辺のコストをcとしたときに逆辺のコストは-cにする (フローを押し戻すとき、コストも押し戻すため）。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int VMAX = 100;
struct Edge {
	int from, to, flow, cost, rev;
	Edge(int from, int to, int flow, int cost, int rev) {
		this->from = from;
		this->to   = to;
		this->flow = flow;
		this->cost = cost;
		this->rev  = rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &g, int from, int to, int flow, int cost) {
	g[from].push_back(Edge(from, to, flow, cost, g[to].size()));
	g[to].push_back(Edge(to, from, 0, -cost, g[from].size() - 1));
}

int dfs(Graph &g, int s, int t, int flow, bool yet[], int level[]) {
	yet[s] = false;
	if (s == t) return flow;
	for (int i = 0; i < g[s].size(); i++) {
		int v = g[s][i].to;
		if (g[s][i].flow > 0 && yet[v] && level[v] == level[s] + g[s][i].cost) {
			int res = dfs(g, v, t, min(flow, g[s][i].flow), yet, level);
			if (res > 0) {
				int r = g[s][i].rev;
				g[s][i].flow -= res;
				g[v][r].flow += res;
				return res;
			}
		}
	}
	return 0;
}

int minCostflow(Graph &g, int s, int t, int flow) {
	const int INF_DIST = 11451419;
	const int INF_FLOW = 11451419;
	const int ERROR_RETURN = -1;
	int level[VMAX];
	bool yet[VMAX];
	queue<int> que;
	int i;
	int ret = 0;
	
	while (true) {
		for (i = 0; i < g.size(); i++) level[i] = INF_DIST;
		que.push(s); level[s] = 0;
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (i = 0; i < g[v].size(); i++) {
				int nv = g[v][i].to;
				if (g[v][i].flow > 0 && level[nv] > level[v] + g[v][i].cost) {
					level[nv] = level[v] + g[v][i].cost;
					que.push(nv);
				}
			}
		}
		if (level[t] >= INF_DIST) break;
		
		while (true) {
			for (i = 0; i < g.size(); i++) yet[i] = true;
			int f = dfs(g, s, t, INF_FLOW, yet, level);
			if (f == 0) break;
			flow -= f;
			ret += f * level[t];
			if (flow <= 0) {
				ret += flow * level[t];
				return ret;
			}
		}
	}
	return -1;
}

int n, m, f;
int u, v, c, d;
Graph g;

int main() {
	cin >> n >> m >> f;
	g.resize(n);
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> c >> d;
		add_edge(g, u, v, c, d);
	}
	cout << minCostflow(g, 0, n - 1, f) << endl;
	return 0;
}