Graphs Project

//подключаем заголовочные файлы и настраиваем работу с пространством имен
#include <iostream> // для ввода и вывода данных
#include <fstream> // для работы с файлами
#include <vector> // для работы с вектором (динамическим массивом)
#include <string> // для работы со строками (текстовыми данными)
#include <queue> // для работы с очередью (структурой данных)
using namespace std; // пространство имен

// в программе для того чтобы вместо одного длинного выражения писать другое, короткое
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;

// переменная - константа, обозначающая в программе "бесконечноть"
const int INF =  1e9 + 7;

// головная функция (здесь реализация нашей основной программы)
int main()
{
    // V - число вершин в графе (число городов)
    // s - число, обозначающее порядковый номер города в таблице (считаем с НУЛЯ)
    // w - переменная, в которую мы будем по циклу записывать данные из таблицы (расстояние между городами)
    int V = 11, s = 7, w;

    // создаем вектор - массив списков и вектор городов
    vector <vii> AdjList;
    vector <string> cities(V);

    // создаем файловый поток вывода данных из файла
    ifstream fin ("graphs.txt");

    // "конструируем" все элементы вектора AdjList
    AdjList.assign(V, vii());

    // по циклу выводим из файла первую строку с именами городов и вводим их в вектор
    for (int i = 0; i < V; i++)
        fin >> cities[i];

    // по циклу выводим из файла оставшиеся данные
    for (int i = 0; i < V; ++i)
    {
        // сюда записываются города как первые элементы в строке, они нам НЕ НУЖНЫ, города мы уже записали
        string name; fin >> name;

        // здесь в w записываются данные из таблицы
        for (int j = 0; j < V; ++j)
        {
            fin >> w;

            // в скобках w <=> w != 0
            if (w) AdjList[i].push_back(ii(j, w));
        }
    }

    ////////////////////////////////////////////////////////////////////
    ///
    ///   АЛГОРИТМ ДЕЙКСТРЫ
    ///
    ////////////////////////////////////////////////////////////////////

    // объявляем вектор, содержащий расстояния от вершины S до всех других вершин в графе
    // расстояние от S до S равно 0
    vi dist(V, INF); dist[s] = 0;

    // вектор путей из Саратова до определенного города
    vector <vector <string>> ways(V);

    // создаем особую структуру - приоритетную очередь, добавляем в нее первый элемент - пару (0, s)
    priority_queue <ii, vector<ii>, greater<ii>> pq; pq.push(ii(0, s));

    // цикл работает до тех пока очередь НЕ пуста
    while (!pq.empty())
    {
        // создаем пару front, в нее записываем начало очереди (ее первый элемент), удаляем пару из очереди
        ii front = pq.top(); pq.pop();

        // в эти переменные записываем первый и второй элементы пары front соответственно
        int d = front.first, u = front.second;

        // если условие выполняется переходим к следующей итерации в цикле
        if (d > dist[u]) continue;

        // по циклу проводим следующие действия
        for (int j = 0; j < AdjList[u].size(); j++)
        {
            // создаем пару v = (j, w), где w - расстояние от u до j
            ii v = AdjList[u][j];

            // если условие выполняется, то выполяем следующие действия
            if (dist[u] + v.second < dist[v.first])
            {
                // записываем в dist[v.first] более малое расстояние, которое нашлось при выполнении программы
                dist[v.first] = dist[u] + v.second;

                // добавляем в очередь новую пару
                pq.push(ii(dist[v.first], v.first));

                // находим новый путь от вершины u до u[j]
                ways[v.first] = ways[u]; ways[v.first].push_back(cities[u]);
            }
        }
    }

  //  завершаем все пути прибытием в нужный пункт
  for (int i = 0; i < V; ++i)
      ways[i].push_back(cities[i]);

  // Выводим ответ на экран
  cout << "The distance from " << cities[s] << " to " << cities[2] << " is " << dist[2] << " km.";

  cout << "\nThe way: ";

  // Выводим путь от Саратова до Москвы
  for (int i = 0; i < ways[2].size() - 1; ++i)
      cout << ways[2][i] << " - ";

  cout << ways[2][ways[2].size() - 1];

  // Закрываем поток (работу с файлом)
  fin.close();
  return 0;
}

//graphs.txt
        Kursk    Lipetsk  Moscow   Orel     Penza    Ryazan   Saransk  Saratov  Tambov   Tula     Voronezh
Kursk    0        0        0        164      0        0        0        0        0        0        227
Lipetsk  0        0        437      294      0        265      0        0        135      292      126
Moscow   0        437      0        0        0        199      0        0        459      183      516
Orel     164      294      0        0        0        0        0        0        0        181      347
Penza    0        0        0        0        0        443      148      232      289      0        0
Ryazan   0        265      199      0        443      0        449      0        288      185      0
Saransk  0        0        0        0        148      449      0        0        0        0        0
Saratov  0        0        0        0        232      0        0        0        391      0        511
Tambov   0        135      459      0        289      288      0        391      0        369      221
Tula     0        292      183      181      0        185      0        0        369      0        345
Voronezh 227      126      516      347      0        0        0        511      221      345      0