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>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const int INF = 1e9;

// ????°??????¨???
struct EdgeC{
  int to, cap, cost, rev;
  EdgeC(int to_=0, int cap_ = 0, int cost_ = 0, int rev_ = 0)
	:to(to_), cap(cap_), cost(cost_), rev(rev_){}
};
using GraphC = vector<vector<EdgeC>>;
void add_edge(GraphC& G, int from, int to, int cap, int cost){
  G[from].emplace_back(to, cap, cost, G[to].size());
  G[to].emplace_back(from, 0, -cost, G[from].size()-1);
}

/**
 * ?????????????????????????????????
 * O(FVE)
 * ?§????s, ??????t, ?????????f ???????°??????¨?????? ?????¨??????????????°-INF
 */
int min_cost_flow(GraphC& G, int s, int t, int f){
  int V = G.size();
  vector<int> dist(V);
  vector<int> prevv(V), preve(V);
  int res = 0;
  
  while(f > 0){
	fill(begin(dist), end(dist), INF);
	dist[s] = 0;
	bool update = true;
	while(update){
	  update = false;
	  for(int v=0;v<V;++v){
		if(dist[v] == INF) continue;
		for(unsigned int i=0;i<G[v].size();++i){
		  auto& e = G[v][i];
		  if(e.cap > 0 && dist[v] + e.cost < dist[e.to]){
			dist[e.to] = dist[v] + e.cost;
			prevv[e.to] = v;
			preve[e.to] = i;
			update = true;
		  }
		}
	  }
	}
	if(dist[t] == INF) return -INF;

	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 * dist[t];
	for(int v=t;v!=s;v=prevv[v]){
	  auto& e = G[prevv[v]][preve[v]];
	  e.cap -= d;
	  G[v][e.rev].cap += d;
	}
  }
  
  return res;
}


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

  int V, E, F;
  cin >> V >> E >> F;
  GraphC G(V);
  REP(i,E){
	int u, v, c, d;
	cin >> u >> v >> c >> d;
	add_edge(G, u, v, c, d);
  }
  int res = min_cost_flow(G, 0, V-1, F);
  cout << (res==-INF?-1:res) << endl;

  return 0;
}