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;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}


const int MAX_V = 20000+5;
using CAP = ll;
using COST = ll;
const ll INF = (ll)1e9;

struct State {
  COST dist;
  int pos;
  bool operator < (const State &o) const {
    return dist > o.dist; // reverse order
  }
};
struct Edge{ int to; CAP cap; COST cost; int rev; };
vector<Edge> adj[MAX_V];
COST potential[MAX_V];
COST dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_V];
void clearedge() { REP(i, MAX_V) adj[i].clear(); }
void addedge(int u, int v, CAP cap, COST cost) {
  adj[u].push_back( (Edge){v, cap, cost, (int)adj[v].size() + (u == v)} );
  adj[v].push_back( (Edge){u, 0, -cost, (int)adj[u].size() - 1} );
}

// sからtへ流量 flow を流す最小コストを返す。
// 流せない場合は INF を返す
COST mincost_maxflow(int s, int t, CAP flow) {
  vector<int> vs;
  REP(i, MAX_V) if (adj[i].size()) vs.push_back(i);
  int res = 0;
  for (int v : vs) potential[v] = 0;
  while (flow > 0) {
    for (int v : vs) dist[v] = INF;
    priority_queue<State> q;
    q.push({0, s});
    dist[s] = 0;
    while (!q.empty()) {
      State crt = q.top(); q.pop();
      if (dist[crt.pos] < crt.dist) continue;
      REP(i, adj[crt.pos].size()) {
        const Edge&e = adj[crt.pos][i];
        COST n_dist = crt.dist + e.cost + potential[crt.pos] - potential[e.to];
        if (e.cap > 0 && dist[e.to] > n_dist) {
          dist[e.to] = n_dist;
          prevv[e.to] = crt.pos;
          preve[e.to] = i;
          q.push({dist[e.to], e.to});
        }
      }
    }
    if (dist[t] == INF) return INF;
    for (int v : vs) potential[v] += dist[v];
    CAP f = flow;
    for (int v = t; v != s; v = prevv[v]) {
      f = min(f, adj[prevv[v]][preve[v]].cap);
    }
    for (int v = t; v != s; v = prevv[v]) {
      Edge &e = adj[prevv[v]][preve[v]];
      e.cap -= f;
      adj[v][e.rev].cap += f;
    }
    flow -= f;
    res += f * potential[t];
  }
  return res;
}

int main2() {
  int V = nextLong();
  int E = nextLong();
  int F = nextLong();

  clearedge();
  REP(i, E) {
    int a = nextLong();
    int b = nextLong();
    int c = nextLong();
    int d = nextLong();
    addedge(a, b, c, d);
  }
  ll ans = mincost_maxflow(0, V-1, F);
  if (ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}