// task5.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

 /*
	Задача 8.

	в городе расположена n автобусных остановок, обозначенных числами и
	N 1.2 n; Имеется К автобусных маршрутов, заданных последовательностями
	соседних остановок при движении автобуса в одном направлении:

	M ={1).j2... 11).
	M,={ 122 12м3},

	где І, натуральное

	Написать программу. которая по заданным номерам остановок I и определяет
	наиболее быстрый путь перемещения пассажира с остановки I и остановку J с
	использованием имеющихся маршрутов автобусов при условии, что время
	движения между соседними остановками у всех маршрутов одинаково. Кроме того, автобусы могут двигаться в
	обоих направлениях

 */
#include "pch.h"
#include <iostream>
#include <list>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

vector<vector<pair<int,vector<int> > > > graph;
set<vector<int> > routs; // все найденные пути между заданной парой вершин
vector<int> path; // найденный путь

// поиск в глубину
void dfs(int const& nodeCur, int const& nodeLast)
{
	if (find(path.begin(), path.end(), nodeCur) == path.end())
	{
		path.emplace_back(nodeCur);

		if (nodeCur == nodeLast)
		{
			for (auto const& val : path)
			{
				cout << val << "  ";
			}
			cout << endl;
			routs.emplace(path);
			path.pop_back();
			return;
		}

		for (auto const& val : graph.at(nodeCur - 1))
		{
			dfs(val.first, nodeLast);
		}
		path.pop_back();
	}
}

int main()
{
	// автобусные маршруты
	vector<vector<int> > busRoutes = { { 4, 3, 2, 1 }, // bus # 0
												{ 1, 5, 3, 4 }, // bus # 1
												{ 4, 2, 1 } }; // bus # 2
	// заданные номера остановок
	pair<int, int> endPoints(1, 4);

	// заполнение графа как списка смежности
	int vert = 0;
	do
	{
		++vert;
		for (int r = 0; r < busRoutes.size(); ++r)
		{
			for (int c = 0; c < busRoutes.at(r).size(); ++c)
			{

				if (busRoutes.at(r).at(c) == vert)
				{
					if (graph.size() < vert)
					{
						graph.push_back(vector<pair<int, vector<int>>>());
					}

					if (c > 0)
					{
						auto itLeftNeighbour = find_if(graph.at(vert - 1).begin(), graph.at(vert - 1).end(), [&](auto const& par) {return par.first == busRoutes.at(r).at(c - 1); });
						if (itLeftNeighbour != graph.at(vert - 1).end())
						{
							itLeftNeighbour->second.push_back(r);
						}
						else
						{
							vector<int> v = { r };
							graph.at(vert - 1).emplace_back(busRoutes.at(r).at(c - 1), v);
						}
					}
					if (c < busRoutes.at(r).size() - 1)
					{
						auto itRightNeighbour = find_if(graph.at(vert - 1).begin(), graph.at(vert - 1).end(), [&](auto const& par) {return par.first == busRoutes.at(r).at(c + 1); });
						if (itRightNeighbour != graph.at(vert - 1).end())
						{
							itRightNeighbour->second.push_back(r);
						}
						else
						{
							vector<int> v = { r };
							graph.at(vert - 1).emplace_back(busRoutes.at(r).at(c + 1), v);
						}
					}
				}

			}
		}
	} while (graph.size() == vert);

	// поиск всех путей между парой вершин
	dfs(endPoints.first, endPoints.second);

	/*// вывод найденных путей
	for (auto const& path : routs)
	{
		for (auto const& node : path)
		{
			cout << node << " ";
		}
		cout << endl;
	} //*/



	// для каждого найденного пути -> каждой вершины находим vector исходящих автобусов
	vector<vector<vector<int>>> numbers(routs.size());
	int j = -1;
	for (auto const& path : routs)
	{
		++j;
		for (int i = 0; i < path.size() - 1; ++i)
		{
			auto it = find_if(graph[path[i] - 1].begin(), graph[path[i] - 1].end(), [&](auto const& pr) {return pr.first == path[i + 1]; });
			if (it != graph[path[i] - 1].end())
			{
				numbers[j].push_back(it->second);
			}
		}
	}

	// находим длиннейшие цепи автобусов
	vector<vector<pair<int, int>>> maxNumLen;
	for (int j = 0; j < numbers.size(); ++j)
	{
		for (int i = 0; i < numbers[j].size(); )
		{
			int maxLen = 1;
			vector<pair<int, int>> numLen;
			for (auto const& number : numbers[j][i])
			{
				int len = 0;
				for (int k = i; k < numbers[j].size(); ++k)
				{
					auto it = find(numbers[j][k].begin(), numbers[j][k].end(), number);
					if (it != numbers[j][k].end())
					{
						++len;
					}
					else break;

				}
				numLen.emplace_back(number, len);
			}
			auto it = max_element(numLen.begin(), numLen.end(), [](auto const& pr1, auto const& pr2) {return pr1.second < pr2.second; });
			maxLen = it->second;
			for (auto const& pr : numLen)
			{
				if (pr.second == maxLen)
				{
					if (maxNumLen.size() < j + 1)
					{
						vector<pair<int, int>> v;
						maxNumLen.push_back(v);
					}
					maxNumLen[j].push_back(pr);
					break;
				}
			}
			i += maxLen;
		}
	}




	// веса путей
	vector<int> weights;
	for (int i = 0; i < maxNumLen.size(); ++i)
	{
		int ribs = 0;
		//int transfers = maxNumLen[i].size() - 1;
		for (int j = 0; j < maxNumLen[i].size(); ++j)
		{
			ribs += maxNumLen[i][j].second;
		}
		weights.emplace_back(ribs);
		cout << "rout # " << i << " weight: " << ribs << endl;
	}

	auto it = min_element(weights.begin(), weights.end());
	int ind = it - weights.begin();
	cout << "\nAnswer: \n";
	for (auto const& pr : maxNumLen[ind])
	{
		cout << "bus number: " << pr.first << " ribs count: " << pr.second << endl;
	}
	cout << endl;
	return 0;
}