Пособие/«Пифагоров экспресс (для C++)»

#include <iostream>
#include <vector>

using namespace std;

struct City { // создаём структуру города, которая хранит его координаты
    int x, y;
};

const int INF = (int)2e9; // Устанавливаем значение, которое больше, чем любое из возможных кратчайших расстояний между городами. Оно понадобится для работы алгоритма Дейкстры

vector<City> Cities; // Массив всех городов

int dist(int a, int b) { // dist(a, b) возвращает расстояние между городами a и b. Формула для расстояния взята из условия
    return (Cities[a].x - Cities[b].x) * (Cities[a].x - Cities[b].x) + (Cities[a].y - Cities[b].y) * (Cities[a].y - Cities[b].y);
}

int djikstra(int s, int f) { // djikstra(s, f) возвращает минимальное расстояние между городами s и f
    int n = Cities.size(); // n - кол-во городов
    vector<bool> was(n); // was[i] = true, если кратчайшее расстояние от s-го города до i-го точно определено
    vector<int> d(n, INF); // d[i] = x, если кратчайшее расстояние от s-го города до i-го равняется x
                           // Изначально расстояние от s-го города до всех остальных = INF, чтобы во время улучшения ответа для j-го города (Когда мы делаем d[j] = min(d[j], d[v] + dist(v, j))), расстояние точно обновилось
    d[s] = 0; // расстояние от изначального города до самого себя = 0
    for (int i = 0; i < n - 1; ++i) { // можно не выполнять (n - 1)-ую итерацию цикла, так как на ней точно не изменятся
                                      // значения массива d
        int v = -1; // v - это очередной город на добавление
        for (int j = 0; j < n; ++j) { // проходимся по всем городам
            if (!was[j] && (v == -1 || d[v] > d[j])) { // если j-ый город не взят в множество городов, у которых точно
                                                       // определено кратчайшее расстояние, и пока кандидатов на роль
                                                       // v-го города нет или j-ый выгоднее предыдущего, то в качестве
                                                       // v-го города берём j-ый
                v = j;
            }
        }
        if (v == -1) break; // если больше достижимых из s-ой городов нет, то выходим из цикла
        was[v] = true; // добавляем v-ый город в множество с точно установленными кратчайшими расстояниями
        // пытаемся улучшить кратчайшие расстояния для городов, смежных с v-ым (Мы перебираем все города, так как по условию для любых городов a, b: можно добраться от a до b и от b до a)
        for (int j = 0; j < n; ++j) { // проходимся по всем городам
            // если j-ый город не принадлежит множеству городов, у которых уже определено кратчайшее расстояние, и
            // текущее расстояние, до j-го города больше, чем расстояние до v-го города + кол-во времени на путь v -> j, то
            // обновляем кратчайшее расстояние для j
            if (!was[j]) {
                d[j] = min(d[j], d[v] + dist(v, j));
            }
        }
    }
    return d[f]; // возвращаем минимальное расстояние между городами s и f
}

void solve() {
    int n;
    cin >> n; // считываем кол-во городов в графе
    Cities.resize(n);
    for (int i = 0; i < n; ++i) { // Итерируемся по всем городам из входных данных
        cin >> Cities[i].x >> Cities[i].y; // считываем координаты i-го города
    }
    int s, f;
    cin >> s >> f; // считываем начальный и конечный города
    // так как нумерация городов в задаче идёт с 1, а нам удобнее, чтобы она шла с 0, уменьшаем s и f на 1
    s--;
    f--;
    cout << djikstra(s, f); // выводим искомое время
}

int main() {
    solve();
    return 0;
}