Разбор задачи «Успеть на поезд»

1. Идея

Нужно понять, можно ли добраться из станции s в станцию t не более чем за T минут, если ехать по самому быстрому маршруту.

То есть задача сводится к поиску кратчайшего пути в неориентированном взвешенном графе:

• вершины — станции;
• рёбра — железнодорожные линии;
• вес ребра — время поездки.

Так как все времена w неотрицательны, для поиска минимального времени подходит алгоритм Дейкстры.

После этого остаётся просто сравнить найденное кратчайшее расстояние dist[t] с T:

• если dist[t] <= T, выводим YES;
• иначе NO.

2. Наблюдения

Наблюдение 1. Это именно задача на кратчайший путь

Пассажир выбирает маршрут с минимальным суммарным временем. Значит, нужно найти минимальную сумму весов рёбер от s до t.

Наблюдение 2. Граф неориентированный

Каждая линия двусторонняя, поэтому ребро u - v надо добавлять в обе стороны:

• из u в v,
• из v в u.

Наблюдение 3. Веса неотрицательны

По условию w >= 0, значит алгоритм Дейкстры работает корректно.

Наблюдение 4. Не обязательно искать расстояния до всех вершин

Как только из очереди с приоритетом извлекли вершину t с актуальным расстоянием, можно остановиться: кратчайшее расстояние до неё уже найдено.

Именно это и сделано в эталонном решении.

Наблюдение 5. Нужен тип long long / большие числа

Хотя один вес ребра не больше 1000000, длина пути может быть большой, а T вообще до 10^18, поэтому расстояния нужно хранить в 64-битном типе:

• в C++ — long long;
• в Python обычный int подходит автоматически.

3. Алгоритм

1. Считать n, m, s, t, T.
2. Построить список смежности графа. Для каждой линии u, v, w:
   • добавить (v, w) в список g[u];
   • добавить (u, w) в список g[v].
3. Создать массив расстояний dist, изначально заполненный очень большим числом.
4. Положить dist[s] = 0.
5. Запустить алгоритм Дейкстры с приоритетной очередью:
   • в очереди храним пары (текущее_расстояние, вершина);
   • каждый раз берём вершину с минимальным расстоянием;
   • если запись устарела, пропускаем её;
   • если это вершина t, можно завершить поиск;
   • пытаемся улучшить расстояния до всех соседей.
6. После завершения:
   • если dist[t] <= T, вывести YES,
   • иначе NO.

4. Почему это работает

Обоснуем корректность.

Алгоритм Дейкстры применяется к графам с неотрицательными весами. В этой задаче все времена на рёбрах неотрицательны, значит его можно использовать.

Что хранит dist[v]

В любой момент dist[v] — это лучшее из уже найденных времен пути от s до v.

Когда из очереди извлекается вершина v с расстоянием d, и при этом d == dist[v], это означает, что более короткий путь в v уже не существует. Для графа с неотрицательными весами это стандартное свойство алгоритма Дейкстры.

Почему можно делать релаксации

Если мы находимся в вершине v и есть ребро в to веса w, то путь через v в to имеет длину dist[v] + w. Если это меньше текущего dist[to], то найден более короткий путь, и расстояние нужно обновить.

Почему можно остановиться на вершине t

Как только вершина t извлечена из очереди с актуальным расстоянием, её кратчайшее расстояние уже окончательно найдено. Значит дальнейший поиск не нужен.

Почему ответ верный

После работы алгоритма:

• dist[t] равно длине кратчайшего пути из s в t, если путь существует;
• если пути нет, dist[t] останется очень большим числом.

Поэтому проверка dist[t] <= T точно отвечает на вопрос, успевает ли пассажир на поезд.

5. Сложность

Пусть n — число станций, m — число линий.

• Построение графа: O(m)
• Алгоритм Дейкстры с приоритетной очередью: O((n + m) log n)

Итоговая сложность: O((n + m) log n)

Память: O(n + m)

Это укладывается в ограничения задачи.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

int main() {
    int n, m, s, t;
    long long T;
    cin >> n >> m >> s >> t >> T;

    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int v = pq.top().second;
        pq.pop();

        if (d != dist[v]) {
            continue;
        }

        if (v == t) {
            break;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;
            if (dist[to] > d + w) {
                dist[to] = d + w;
                pq.push({dist[to], to});
            }
        }
    }

    if (dist[t] <= T) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

import heapq

n, m, s, t, T = map(int, input().split())

g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))
    g[v].append((u, w))

INF = 10**30
dist = [INF] * (n + 1)
dist[s] = 0

pq = [(0, s)]

while pq:
    d, v = heapq.heappop(pq)

    if d != dist[v]:
        continue

    if v == t:
        break

    for to, w in g[v]:
        nd = d + w
        if nd < dist[to]:
            dist[to] = nd
            heapq.heappush(pq, (nd, to))

if dist[t] <= T:
    print("YES")
else:
    print("NO")