#include <iostream>
#include <locale.h>
#include <vector>

using namespace std;

const int INF = 0X7FFFFFFF;
const int n = 6;

void out(vector<int> p, int start, int end)
{
	if (end == start)
	{
		cout << end + 1;
		return;
	}
	out(p, start, p[end]);
	cout << '-' <<  end + 1;
	return;
}

int main()
{

	setlocale(LC_ALL, "Russian");
	vector<vector<pair<int, double>>> matr(n);

	matr[0].resize(3);
	matr[0][0].first = 1;
	matr[0][0].second = 3;
	matr[0][1].first = 2;
	matr[0][1].second = 2;
	matr[0][2].first = 3;
	matr[0][2].second = 4;

	matr[1].resize(2);
	matr[1][0].first = 4;
	matr[1][0].second = 2;
	matr[1][1].first = 5;
	matr[1][1].second = 4;

	matr[2].resize(1);
	matr[2][0].first = 4;
	matr[2][0].second = 1;

	matr[3].resize(2);
	matr[3][0].first = 2;
	matr[3][0].second = 1;
	matr[3][1].first = 5;
	matr[3][1].second = 3.5;

	matr[4].resize(1);
	matr[4][0].first = 5;
	matr[4][0].second = 3;


	int start = 0, end = 5;
	vector<int> d(n, INF), p(n);
	d[start] = 0;
	vector<bool> u(n);

	for (int i = 0; i < n; i++)
	{
		int v = -1;
		for (int j = 0; j < n; j++)
			if (!u[j] && (v == -1 || d[j] < d[v]))
				v = j;
		if (d[v] == INF)
			break;
		u[v] = true;

		for (int j = 0; j < matr[v].size(); j++)
		{
			int to = matr[v][j].first;
			int len = matr[v][j].second;
			if (d[v] + len < d[to])
			{
				d[to] = d[v] + len;
				p[to] = v;
			}
		}
	}

	cout << "Путь: ";
	out(p, start, end);

	cout << endl << "Длина пути: " << d[end] << endl;

	system("pause");
	return 0;
}