#include <iostream>
#include <iomanip>
#include <fstream>
#include <locale.h>

#define INF 100000
#define SIZE 15
using namespace std;

int main() {
    setlocale(LC_ALL, "rus");
    int d[SIZE];
    int v[SIZE];
    int G[SIZE][SIZE] = {
        {0, 11, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 13, 0, 0, 0, 0, 0, 0, 23, 0, 0, 0, 0, 0},
        {0, 0, 7, 0, 5, 0, 0, 0, 3, 7, 0, 0, 0, 0, 0},
        {0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {10, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 15, 3, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 13, 0, 0, 0, 23, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 3, 3, 0, 3},
        {0, 0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0}
    };

    cout << "Матрица смежности:" << endl << endl;
    for (int i = -1; i < SIZE; i++) {
        for (int j = -1; j < SIZE; j++) {
            if (i == -1 && j == -1) cout << setw(4) << "";
            else if (i == -1)
                if (j < 10) cout << "___" << j; else cout << "__" << j;
            else if (j == -1) cout << setw(3) << i << "|";
            else cout << setw(4) << G[i][j];
        }
        cout << endl;
    }

    int start;
loop:
    cout << endl << "Введите номер вершины от 0 до " << SIZE - 1 << ", из которой хотите найти кратчайший путь: ";
    cin >> start;
    if (start < 0 || start > SIZE - 1)
    {
        cout << endl << "Выбранная вершина не существует!" << endl;
        goto loop;
    }
    cout << endl;
    for (int i = 0; i < SIZE; i++)
    {
        d[i] = INF;
        v[i] = -1;
    }

    d[start] = 0;
    for (int k = 0; k < SIZE - 1; k++)
        for (int i = 0; i < SIZE; i++)
            for (int j = 0; j < SIZE; j++)
                if (G[i][j] != 0 && (d[i] + G[i][j]) < d[j])
                {
                    d[j] = d[i] + G[i][j];
                    v[j] = i;
                }

    cout << setw(19) << "Вершина:";
    for (int i = 0; i < SIZE; i++)
        cout << setw(4) << i;
    cout << endl << setw(19) << "Предыдущая вершина:";
    for (int i = 0; i < SIZE; i++)
        cout << setw(4) << v[i];
    cout << endl << endl;

    for (int i = 0; i < SIZE; i++)
        if (i == start) cout << "Вершина " << start << " - начальная." << endl;
        else if (d[i] == INF) cout << "Пути из вершины " << start << " в вершину " << i << " не существует." << endl;
        else cout << "Кратчайшее расстояние из вершины " << start << " в вершину " << i << " равно " << d[i] << ", предпоследняя вершина пути: " << v[i] << endl;
    cout << endl;


    return 0;
}