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 <math.h>
#include <bits/stdc++.h>//一括で読み込み
using namespace std;
#define MAX_V 500
typedef long long ll;
typedef pair<int,int> P;
struct edge{int to, cap, cost, rev;};
 
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
 
void add_edge(int from, int to, int cap, int cost)
{
  G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
  G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1});
}
 
int min_cost_flow(int s, int t, int f)
{
  int res = 0;
  fill(h, h+V, 0);
  while(f > 0)
  {
    priority_queue<P,vector<P>,greater<P>> que;
    fill(dist, dist+V, 1<<28);
    dist[s] = 0;
    que.push(P(0,s));
    while(!que.empty())
    {
      P p = que.top();
      que.pop();
      int v = p.second;
      if(dist[v] < p.first) continue;
      for(int i = 0; i < G[v].size(); i++)
      {
        edge &e=G[v][i];
        if(e.cap > 0 && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to])
        {
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(P(dist[e.to], e.to));
        }
      }
    }
    if(dist[t] == (1 << 28))
    {
      return -1;
    }
    for(int v = 0; v < V; v++) h[v] += dist[v];
 
    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*h[t];
    for(int v = t; v != s; v = prevv[v])
    {
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}
 
int main()
{
  int e,f,u,v,c,d,i;
  cin >> V;//Vは頂点数（500以下）
  cin >> e >> f;
  for(i = 0; i < e; i++)
  {
    cin >> u >> v >> c >> d;
    add_edge(u,v,c,d);//辺の追加（開始、終了頂点と容量、コスト）
  }
  cout << min_cost_flow(0, V-1, f) << endl;//最小費用流(開始、終了頂点と流量)
  return 0;
}