#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <locale.h>
#include <vector>
#include <fstream>

using namespace std;

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

int Translate(char* c)
{
	int n = 0;
	while(isdigit(*c))
	{
		n *= 10;
		n += (*c - '0');
		c++;
	}
	return n;
}

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 = 8;

	const char* inFileName = "in.txt";

	char** mas = new char*[19];
	for (int i = 0; i < 19; i++)
		mas[i] = new char[7];

	FILE* file = fopen(inFileName, "rb");

	if (file == NULL)
	{
		perror("Ошибка открытия фйла");
		return -1;
	}

	int arr[9];
	for (int i = 0; i < 9; i++)
		arr[i] = 0;

	fseek(file, 0, SEEK_SET);
	for (int i = 0; i < 19; i++)
	{
		fread(mas[i], 1, 7, file);
		fseek(file, 2, SEEK_CUR);
		arr[Translate(mas[i])] += 1;
	}

	for (int i = 0; i < 9; i++)
		matr[i].resize(arr[i]);
	int i = 0, k = 0;
	while (i < 19)
	{
		int count = 0;

		while (Translate(mas[i]) == k)
		{
			mas[i] += 2;
			matr[k][count].first = Translate(mas[i]);
			mas[i] += 2;
			matr[k][count].second = Translate(mas[i]);
			count++;
			i++;
			if (i == 19)
				break;
		}
		k++;
	}

	/*
	for (int i = 0; i < 19; i++)
	{
		int k = Translate(mas[i]);
		mas[i] += 2;
		matr[k][arr[k]].first = Translate(mas[i]);
		mas[i] += 2;
		matr[k][arr[k]].second = Translate(mas[i]);
		arr[k] += 1;
	}*/

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