#include <iostream>
#include <conio.h>
#include <windows.h>
#include<iomanip>
#include <cstdlib>

using namespace std;
char NEWT[256];
char*RUS(char*TEXT) {
	CharToOemA(TEXT, NEWT);
	return NEWT;
}

int v;
int main()
{
	int i, j;
	int infinity = 1000;
	int VES[100][100];
	int x[100];
	int DlinaPuti[100];
	int PredVertex[100];
	int VERTEX;
	int p;
	cout<<RUS("Ввести количество вершин в графе ")<<endl;
	cin>>VERTEX; p = VERTEX;
	cout<<RUS("Заполните матрицу весов графа ")<<endl;
	cout<<setw(4);
	for (i = 0; i<VERTEX; i++)
		cout<<RUS("|x")<<i + 1;
	cout<<endl;

	for (i = 0; i<VERTEX; i++)
	{
		cout<<RUS("X")<<i + 1<<'|';
		for (j = 0; j<VERTEX; j++)
			cin>>VES[i][j];
	int start;
	int end;
N: cout<<RUS("Введите стартовую вершину: ");
	cin>>start;
	if (start>(p - 1) && start<0) { cout<<RUS("Нет такой вершины повторите ввод...")<<endl; goto N; }
	start = start - 1;
	for (int prosto = 0; prosto<VERTEX; prosto++)
	{
		end = prosto;
		if (end == start) continue;
		else
		{


			int u;
			for (u = 0; u<p; u++)
			{
				DlinaPuti[u] = infinity;

				x[u] = 0;
			}
			PredVertex[start] = 0;
			DlinaPuti[start] = 0;
			x[start] = 1;
			v = start;

			while (1)
			{

				for (u = 0; u<p; u++)
				{
					if (VES[v][u] == 0)continue;
					if (x[u] == 0 && DlinaPuti[u]>DlinaPuti[v] + VES[v][u])

					{
						DlinaPuti[u] = DlinaPuti[v] + VES[v][u];

						PredVertex[u] = v;

					}
				}
				int w = infinity;
				v = -1;
				for (u = 0; u<p; u++)
				{
					if (x[u] == 0 && DlinaPuti[u]<w)


					{
						v = u;
						w = DlinaPuti[u];
					}
				}
				if (v == -1)
				{
cout<<RUS("Нет пути из вершины ")<<start + 1; cout<<RUS(" в вершину ")<<end + 1<<"."<<endl;
					break;
				}
				if (v == end)
				{
cout<<RUS("Кратчайший путь из вершины ")<<start + 1; cout<<RUS(" в вершину ")<<end + 1<<":";
					u = end;
					while (u != start)
					{
						cout<<" "<<u + 1;
						u = PredVertex[u];
					}
					cout<<" "<<start + 1<<RUS(". Длина пути - ")<< DlinaPuti[end]; cout<<endl;
					break;
				}
				x[v] = 1;
			}
		}
	}
	system("pause");
	return 0;
}