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

	/// One of the @link comparison_functors comparison functors@endlink.
	struct greater_pair_second: public binary_function<pair<int, int>, pair<int, int>, bool>
	{
		bool operator()(const pair<int, int>& __x, const pair<int, int>& __y) const
		{
			return __x.second > __y.second;
		}
	};

	struct pair_less_first_less_second
	{
		bool operator()(const pair<int, int>& __x, const pair<int, int>& __y) const
		{
			if (__x.first < __y.first) return true;
			if (__x.first > __y.first) return false;
			if (__x.first == __y.first) return __x.second < __y.second;
			
			return true; //never happen, just to avoid indexer's warning
		}
	};

	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)
		{
			// 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])
			{
				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_initial;
		best_cost_initial.resize(N + 1);

		find_best_cost_bellman_ford(S, adj_list, best_cost_initial);

		set<pair<int, int>, pair_less_first_less_second> Q;
		vector<int> best_cost;
		vector<char> in_queue;
		vector<Edge*> parent_edges;

		best_cost.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.begin(), best_cost.end(), std::numeric_limits<int>::max());
			best_cost[S] = 0;
			for (int u = 1; u <= N; u++)
				Q.insert(make_pair(best_cost[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())
			{
				int u = Q.begin()->second;
				//pop the first element in the set
				Q.erase(Q.begin());
				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[u] + e->z + best_cost_initial[u]
								- best_cost_initial[v];
						if (augmented_cost_uv < best_cost[v])
						{
							int prev_cost_v = best_cost[v];
							best_cost[v] = augmented_cost_uv;
							//update the cost of the node in the set							
							auto it = Q.find(make_pair(prev_cost_v, v));
							Q.erase(it);
							Q.insert(make_pair(best_cost[v], v));
							
							parent_edges[v] = e;
						}
					}
				}
			}

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