#include <iostream>
#include<iostream>
#include<windows.h>
#include<conio.h>
#include<stdio.h>
#include<locale.h>
#include<math.h>
using namespace std;

const int n = 5;

int a[n][n] = { {0,0,5,0,20},{0,0,0,10,12},{5,0,0,0,0},{0,10,0,0,0},{20,12,0,0,0} };
int b[n][n];
//void way(int i0, int j0);
int otk, kud;

void way(int i0, int j0){
	printf("%i -> ", i0);
	while (a[i0-1][j0-1] != b[i0-1][j0-1]) {
		for (int i = 0; i < n; ++i){
			for (int j = 0; j < n; j++){
				if ((i != i0-1) && (j != j0-1) && (a[i0-1][i] != 0) && (b[i][j0-1] != 0) && (b[i0-1][j0-1] == (a[i0-1][i] + b[i][j0-1]))) {
					printf("%i(%i) -> ", i+1, a[i0-1][i]);
					i0 = i+1;
					break;
				}
			}
		}
	}
	printf("%i(%i)", j0, a[i0-1][j0-1]);
}

int main(){

	setlocale(LC_ALL, "Russian");

	int n = 5;

	cout << "Матрица а" << endl;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++) printf("%3.1d ", a[i][j]);
		cout << endl;
	}
	cout << endl;

	cout << "Матрица b (копия матрицы a)" << endl;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++) {
			b[i][j] = a[i][j];
			printf("%3.1d ", b[i][j]);
		}
		cout << endl;
	}
	cout << endl;


	while (1){
		int is = 0;

		for (int i = 0; i < n; ++i){
			for (int j = 0; j < n; j++){
				if (i != j && b[i][j] != 0){
					for (int k = 0; k < n; ++k){

						if (k != i && k != j && b[j][k]){
							if (b[i][k] == 0 || b[i][k] > b[i][j] + b[j][k]){
								b[i][k] = b[i][j] + b[j][k];
								is = 1;
							}
						}
					}
				}
			}
		}
		if (is == 0) break;
	}

	cout << endl;

	cout << "Измененная матрица b" << endl;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			printf("%3.1d ", b[i][j]);
		}
		cout << endl;
	}
	cout << endl;

	cout << "Откуда -> куда" << endl;
	int otk; int kud;
	cin >> otk >> kud;
	way(otk, kud);

	_getch();
	return 0;
}