/*
 * e_032_max_flow_min_cost_modified_for_dijsktra.cpp
 *
 *  Created on: May 17, 2015
 *      Author: Marius
 */

#include <iostream>
#include <utility>
using namespace std;
#include <fstream>
#include <queue>
#include <list>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>
#include <set>

#ifdef __BLOCK_TIMERS
#include "util/BlockTimer.h"
#else
class BlockTimerC
{
public:
    BlockTimerC(std::string a) : a(a)
    {}
protected:
    std::string a;
};
#endif

namespace e_032_max_flow_min_modified_for_dijsktra_nms
{
    struct Edge
    {
        int u, v; // edge u to v
        int c; // the capacity
        int z; // the cost of the edge
        int dir; // direction: forward (1) or backward (-1) edge
        Edge* re; // pointer to the reverse edge in the graph
    };

    void find_best_cost_bellman_ford(int S, vector<vector<Edge*>>& adj_list, vector<int>& best_cost)
    {
        int N = adj_list.size() - 1;
        list<int> Q;
        vector<char> in_queue;
        in_queue.resize(N + 1);

        std::fill(best_cost.begin(), best_cost.end(), std::numeric_limits<int>::max());
        std::fill(in_queue.begin(), in_queue.end(), 0);

        Q.push_back(S);
        in_queue[S] = 1;
        best_cost[S] = 0;

        //while ( !Q.empty() && max_bfs_level <= N )
        // the problem statement guarantees there are no negative cycles
        while (!Q.empty())
        {
            // pop one element from the list
            int u = Q.front();
            Q.pop_front();
            in_queue[u] = 0;

            //parse the adjacency list and look for possible better costs
            for (Edge* e : adj_list[u])
            {
                if (e->c <= 0) continue; //only positive capacities are processed here

                int v = e->v;
                int candidate_cost = best_cost[u] + e->z;
                if (candidate_cost < best_cost[v])
                {
                    best_cost[v] = candidate_cost;
                    if (!in_queue[v])
                    {
                        Q.push_back(v);
                        in_queue[v] = 1;
                    }
                }
            }

        }
    }

    int find_max_flow_ford_fulkerson(int N, int S, int D, vector<vector<Edge*>>& adj_list,
            int& total_cost)
    {
        int max_flow = 0;
        total_cost = 0;

        //find the initial best cost using the bellman ford algorithm
        //the algorithm only uses the cost and ignores the capacities of the edges
        vector<int> best_cost_prev, best_cost_new;
        best_cost_prev.resize(N + 1);
        best_cost_new.resize(N + 1);

        find_best_cost_bellman_ford(S, adj_list, best_cost_prev);

        typedef pair<int, int> p_ii;
        priority_queue<p_ii, vector<p_ii>, std::greater<p_ii>> Q;
        vector<int> best_cost_augmented;
        vector<char> in_queue;
        vector<Edge*> parent_edges;

        best_cost_augmented.resize(N + 1);
        in_queue.resize(N + 1);
        parent_edges.resize(N + 1);

        std::fill(best_cost_new.begin(), best_cost_new.end(), std::numeric_limits<int>::max() / 2);

        bool has_s2t_path = true;
        while (has_s2t_path)
        {
            //Dijkstra
            std::fill(best_cost_augmented.begin(), best_cost_augmented.end(),
                    std::numeric_limits<int>::max() / 2);

            best_cost_augmented[S] = 0;
            best_cost_new[S] = 0;

            for (int u = 1; u <= N; u++)
                Q.push(make_pair(best_cost_augmented[u], u));

            std::fill(in_queue.begin(), in_queue.end(), 1);

            for (Edge*& ep : parent_edges)
                ep = 0;

            //find a path from source to sink in the residual graph
            //only edges with positive capacities should be included in the path
            while (!Q.empty())
            {
                //pop the first element in the set
                p_ii top = Q.top();
                int u = top.second;
                int c = top.first;
                Q.pop();

                //if not the true minimum, do nothing
                //take care about multiple costs for the same node in the priority queue
                if (c > best_cost_augmented[u]) continue;

                in_queue[u] = 0; // no longer in queue

                for (Edge* e : adj_list[u])
                {
                    int v = e->v, cap_uv = e->c, cost_uv = e->z;
                    //edge with positive capacity
                    if (cap_uv > 0 && in_queue[v])
                    {
                        //check-update the cost of the node
                        int augmented_cost_uv = best_cost_augmented[u] + cost_uv + best_cost_prev[u]
                                - best_cost_prev[v];

                        if (augmented_cost_uv < best_cost_augmented[v])
                        {
                            //update the cost of the node							
                            best_cost_augmented[v] = augmented_cost_uv;

                            //insert the updated cost
                            //take care, the previous best cost, is still in the priority queue
                            Q.push(make_pair(best_cost_augmented[v], v));

                            parent_edges[v] = e;

                            //update the real best cost
                            best_cost_new[v] = best_cost_new[u] + cost_uv;
                        }
                    }
                }
            }

            //prepare the updated cost for the next iteration
            //for (int i = 1; i <= N; i++)
                //best_cost_prev[i] = best_cost_new[i];
            best_cost_prev = best_cost_new;

            //if the sink was reached, there is a path from source to sink
            //the path is the shortest, due to the bellman-ford algorithm
            if (parent_edges[D] != 0)
            {
                // we have a path from source to sink
                // update the residual graph
                //
                // parse the path we have found from sink to source, via parent edges
                // and find the minimum capacity
                int min_capacity = parent_edges[D]->c + 1;
                int node = D;
                while (node != S)
                {
                    Edge* e = parent_edges[node];
                    min_capacity = min(min_capacity, e->c);
                    node = e->u;
                }
                //increment the flow value
                max_flow += min_capacity;

                //update the capacity of edges in the residual graph
                node = D;
                while (node != S)
                {
                    Edge* e = parent_edges[node];
                    e->c -= min_capacity;
                    //also update the reverse edge
                    e->re->c += min_capacity;

                    //update the total cost
                    total_cost += min_capacity * e->z;

                    node = e->u;
                }
            }
            else
                has_s2t_path = false; //no more paths from s to t
        }

        return max_flow;
    }
}

//int e_032_max_flow_min_modified_for_dijsktra()
int main()
{
    using namespace e_032_max_flow_min_modified_for_dijsktra_nms;

    string in_file = "fmcm.in";
    string out_file = "fmcm.out";

    int N, M, S, D;
    vector<vector<Edge*>> adj_list;

    {
        BlockTimerC bc("Inputs");
        ifstream ifs(in_file.c_str());
        if (!ifs.is_open())
        {
            cout << "Input file not found" << endl;
            return -1; // no input file
        }
        ifs >> N >> M >> S >> D;

        adj_list.resize(N + 1);

        for (int m = 1; m <= M; m++)
        {
            //create the forward and it's backward edge
            Edge* e = new Edge;
            Edge* re = new Edge;

            ifs >> e->u >> e->v >> e->c >> e->z;
            e->dir = 1;
            e->re = re;

            re->u = e->v;
            re->v = e->u;
            re->c = 0;
            re->z = -e->z;
            re->dir = -1;
            re->re = e;

            adj_list[e->u].push_back(e);
            adj_list[e->v].push_back(re);
        }

        ifs.close();
    }

    int total_cost;
    {
        BlockTimerC bc("Algorithm");
        find_max_flow_ford_fulkerson(N, S, D, adj_list, total_cost);
    }

    {
        BlockTimerC bc("Outputs");
        ofstream ofs(out_file.c_str());
        //ofs << max_flow << ", " << total_cost;
        ofs << total_cost;
        ofs.close();
    }

    {
        BlockTimerC bc("Cleanup");
        //release the memory
        for (int u = 1; u <= N; u++)
            for (vector<Edge*>::iterator it = adj_list[u].begin(); it != adj_list[u].end(); it++)
                delete *it;
    }
    return 0;
}