#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>

const int infinity = INT_MAX;  //обозначение несуществующего пути из одной вершины в другую


class Graph {
    typedef std::pair<int, char> p_type; //здесь храним длину пути и вершину, через который мы этот путь будем корректировать
    size_t size;  //размер графа (кол-во вершин)
    p_type **matrix;  //матрица смежности
    std::vector<char> V;  //вектор вершин
public:
    //конструктор графа (надо переделать со вводом из файла)
    Graph(std::istream &in) {
        in >> size;

        int x = 0;
        char tmp;
        while (x != size) {
            in >> tmp;
            V.push_back(tmp);
            x++;
        }

        matrix = new p_type*[size];
        for (size_t i = 0; i < size; ++i) matrix[i] = new p_type[size];
        for (size_t i = 0; i < size; ++i) {
            for (size_t j = 0; j < size; ++j) {
                in >> matrix[i][j].first;
                matrix[i][j].second = V[j];
            }
        }
    }

    //вывод матрицы на экран
    void show() {
        for (size_t i = 0; i < size; ++i) {
            for (size_t j = 0; j < size; ++j) {
                std::cout << matrix[i][j].first << "," << matrix[i][j].second << " ";
            }
            std::cout << std::endl;
        }
    }

    //дальше методы нашего алгоритма
    void alg_floyd() {
        int x;
        for (size_t k = 0; k < size; ++k) {
            for (size_t i = 0; i < size; ++i) {
                for (size_t j = 0; j < size; ++j) {
                    if ((k == i) || (k == j) || (i == j)
                        || (matrix[i][k].first == infinity) || (matrix[k][j].first == infinity)) continue;
                    if (matrix[i][j].first >= (matrix[i][k].first + matrix[k][j].first)) {
                        x = (matrix[i][k].first + matrix[k][j].first);
                        matrix[i][j].first = x;
                        matrix[i][j].second = V[k];
                    }
                }
            }
        }
    }

    void short_path(char x, char y) {
        std::cout << x;
        short_path_main(x, y);
        std::cout << y;
    }

    void short_path_main (char x, char y) {
        int help_x, help_y;
        help_x = help_y = -1;
        for (int i = 0; i < size; ++i) {
            if (V[i] == x) help_x = i;
            if (V[i] == y) help_y = i;
            if ((help_x >= 0) && (help_y >= 0)) break;
        }
        if ((matrix[help_x][help_y].second == y) || (matrix[help_x][help_y].second == x)) return;
        std::cout << matrix[help_x][help_y].second;

        if (matrix[help_x][help_y].second != x) {
            short_path_main(x, matrix[help_x][help_y].second);
            short_path_main(matrix[help_x][help_y].second, y);
        }
    }


};

int main()
{
    std::ifstream in("input.txt");
    Graph object(std::cin);
    object.show();
    std::cout << "\n\n";
    object.alg_floyd();
    object.show();
    std::cout << "Enter vershini: \n";
    char x, y;
    std:: cin >> x >> y;
    object.short_path(x, y);

    system("pause");
    return 0;
}