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<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define INF 200000000

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

#define VMAX 100

struct OwnEdge
{
	int f, t, flow, cap,cost;
	OwnEdge(int f, int t, int flow, int cap,int cost) :f(f), t(t), flow(flow), cap(cap),cost(cost) {}
};

vector<OwnEdge> G[VMAX];
int h[VMAX], tod[VMAX], prevv[VMAX], preve[VMAX];

int solve(int n, int src, int dest, int F)
{
	int ans = 0;
	while (F > 0)
	{
		fill(tod, tod + VMAX, INF);
		priority_queue<pii, vector<pii>, greater<pii>> pq;
		tod[src] = 0;
		pq.push(make_pair(0, src));
		while (!pq.empty())
		{
			pii temp = pq.top();
			pq.pop();
			if (tod[temp.second] < temp.first)
			{
				continue;
			}
			for (int i = 0; i != G[temp.second].size(); i++)
			{
				if (G[temp.second][i].cap <= G[temp.second][i].flow)
				{
					continue;
				}
				if (tod[G[temp.second][i].t] + h[G[temp.second][i].t]>tod[temp.second] + h[temp.second] + G[temp.second][i].cost)
				{
					tod[G[temp.second][i].t] = tod[temp.second] + h[temp.second] + G[temp.second][i].cost - h[G[temp.second][i].t];
					prevv[G[temp.second][i].t] = temp.second;
					preve[G[temp.second][i].t] = i;
					pq.push(make_pair(tod[G[temp.second][i].t], G[temp.second][i].t));
				}
			}
		}

		if (tod[dest] == INF)
		{
			return -1;
		}

		for (int i = 0; i < n; i++)
		{
			h[i] += tod[i];
		}
		int td = F;
		for (int i = dest; i != src; i = prevv[i])
		{
			td = min(td, G[prevv[i]][preve[i]].cap - G[prevv[i]][preve[i]].flow);
		}
		F -= td;
		ans += td*h[dest];
		for (int i = dest; i != src; i = prevv[i])
		{
			G[prevv[i]][preve[i]].flow += td;
			G[i][G[prevv[i]][preve[i]].f].flow -= td;
		}
	}
	return ans;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int V, E, F;
	cin >> V >> E >> F;

	for (int i = 0; i < E; i++)
	{
		int u, v, c, d;
		cin >> u >> v >> c >> d;

		int tus = G[u].size(), tvs = G[v].size();

		G[u].push_back(OwnEdge(tvs, v, 0, c, d));
		G[v].push_back(OwnEdge(tus, u, c, c, -d));
	}

	cout << solve(V, 0, V - 1, F) << endl;

	return 0;
}