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 <vector>
#include <queue>
#include <set>
using namespace std;

struct Graph {
  struct edge {
    int to;
    int cap;
    int cost;
    int rev;
  };

  int n;
  vector<vector<edge>> edges;

  Graph(int N) {
    n = N;
    edges.resize(n, vector<edge>());
  }

  int size() const { return n; }

  vector<edge> &operator[](int v) { return edges[v]; }
};


int minimumCostFlow(Graph& g,int s,int t,int f)
{
    const int n = g.size();
    using Pi = pair<int,int>;
    priority_queue<Pi,vector<Pi>,greater<Pi>> que;
    vector<int> prevv(n,-1);
    vector<int> preve(n,-1);
    vector<int> potential(n,0);
    int res = 0;
    while(f > 0){
        vector<int> dist(n,1e9);
        que.push({0,s});
        dist[s] = 0;
        while(!que.empty()){
            Pi p = que.top();
            que.pop();
            if(dist[p.second] < p.first) continue;
            for(int i = 0;i < g[p.second].size();i++){
                auto& e = g[p.second][i];
                int next = dist[p.second] + e.cost + potential[p.second] - potential[e.to];
                if(e.cap > 0 && dist[e.to] > next){
                    dist[e.to] = next;
                    prevv[e.to] = p.second;
                    preve[e.to] = i;
                    que.push({dist[e.to],e.to});
                }
            }
        }
        if(dist[t] == 1e9) return -1;
        for(int v = 0;v < n;v++){
            potential[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 * potential[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;
}

#include <iostream>

int main()
{
    int v;int e;int f;
    cin >> v >> e >> f;

    Graph g(v);
    for(int i = 0;i < e;i++)
    {
        int u,v,c,d;
        cin >> u >> v >> c >> d;
        g[u].push_back({v,c,d,(int)g[v].size()});
        g[v].push_back({u,0,-d,(int)g[u].size() - 1});
    }

    int ans = minimumCostFlow(g,0,v - 1,f);
    cout << ans << endl;
}