/*
 * e_032_max_flow_ford_fulkerson.cpp
 *
 *  Created on: May 16, 2015
 *      Author: Marius
 */

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

namespace e_032_max_flow_min_cost_bellman_ford_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
	};

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

		list<int> Q;
		vector<int> best_cost; // best cost for each node
		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)
		{
			//no node on the path at the beginning
			Q.clear();
			std::fill(in_queue.begin(), in_queue.end(), 0);
			std::fill(best_cost.begin(), best_cost.end(), std::numeric_limits<int>::max());
			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
			Q.push_back(S);
			in_queue[S] = 1;
			best_cost[S] = 0;
			while (!Q.empty())
			{
				int u = Q.front();
				Q.pop_front();
				in_queue[u] = 0; // no longer in queue
				for (auto e : adj_list[u])
				{
					//edge with positive capacity
					if (e->c > 0)
					{
						int v = e->v;
						//check-update the cost of the node
						int cost_uv = best_cost[u] + e->z;
						if (cost_uv < best_cost[v])
						{
							best_cost[v] = cost_uv;
							//put the node in the list if not already there
							if (!in_queue[v])
							{
								Q.push_back(v);
								in_queue[v] = 1;
							}
							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_cost_bellman_ford()
int main()
{
	using namespace e_032_max_flow_min_cost_bellman_ford_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
				if (flow_e > 0) 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;
}