/*
 * 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>

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;
        vector<int> bfs_levels; // the level of the nodes in a bfs search from S
        in_queue.resize(N + 1);
        bfs_levels.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;
        bfs_levels[S] = 1;
        int max_bfs_level = 1;

        //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 (auto 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;
                    bfs_levels[v] = bfs_levels[u] + 1;
                    max_bfs_level = max(bfs_levels[v], max_bfs_level);

                    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 max_flow = 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> pii;
        priority_queue<pii, vector<pii>, std::greater<pii>> 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);

        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);
            std::fill(best_cost_new.begin(), best_cost_new.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 (auto& 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
                auto& 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 (auto e : adj_list[u])
                {
                    int v = e->v;
                    //edge with positive capacity
                    if (in_queue[v] == 1 && e->c > 0)
                    {
                        //check-update the cost of the node
                        int augmented_cost_uv = best_cost_augmented[u] + e->z + 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] + e->z;
                        }
                    }
                }
            }

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

            //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;
                    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;

    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();

    find_max_flow_ford_fulkerson(N, S, D, adj_list);

    //find the cost of the flow
    int total_cost = 0;
    for (int u = 1; u <= N; u++)
    {
        for (auto e : adj_list[u])
        {
            // the flow of the edge is the capacity of the forward edge minus 
            // the capacity of the backward edge
            if (e->dir == 1)
            {
                int flow_e = e->re->c;
                //if the edge has flow, add the cost of the edge to the total cost
                total_cost += flow_e * e->z;
            }
        }
    }

    ofstream ofs(out_file.c_str());
    //ofs << max_flow << ", " << total_cost;
    ofs << total_cost;
    ofs.close();

    //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;
}