1. Идея

Нужно найти кратчайшее время пути из вершины 1 в вершину n, но с дополнительным ограничением: суммарная стоимость автобусных поездок не должна превышать B.

Если бы автобусов не было, это была бы обычная задача на кратчайший путь. Если бы у автобусов была только длина, но не было стоимости, тоже подошёл бы обычный алгоритм Дейкстры.

Но здесь состояние зависит не только от текущего места, но и от того, сколько монет уже потрачено. Поэтому будем искать кратчайший путь не просто по вершинам, а по состояниям вида:

• вершина
• потрачено монет

То есть dist[v][b] — минимальное время, за которое можно попасть в место v, потратив ровно b монет.

После этого применим Дейкстру по таким состояниям.

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

Наблюдение 1. Пешие тропы не меняют бюджет

Если мы идём по пешей тропе из u в v за w минут, то количество потраченных монет не меняется.

Значит, из состояния (u, b) можно перейти в (v, b) с добавлением w ко времени.

Наблюдение 2. Автобус меняет и время, и потраченные монеты

Если есть автобус из u в v за t минут и стоимостью c, то из состояния (u, b) можно перейти в (v, b + c), если b + c <= B.

Наблюдение 3. Все веса положительные

И времена на пеших тропах, и времена автобусных поездок положительны. Значит, для графа состояний можно использовать алгоритм Дейкстры.

Наблюдение 4. Ответ — минимум по всем допустимым тратам

Нас не просят потратить ровно B монет. Нужно уложиться в бюджет, то есть потратить не более B.

Поэтому ответом будет:

• минимум среди dist[n][0], dist[n][1], ..., dist[n][B].

3. Алгоритм

Построим два списка рёбер:

• walk[u] — пешие тропы из u, каждая имеет вид (to, w)
• bus[u] — автобусные рейсы из u, каждый имеет вид (to, t, c)

Далее:

1. Создадим массив dist размера (n + 1) x (B + 1).

   • dist[v][b] — минимальное время добраться до v, потратив b монет.
   • Изначально всё равно бесконечности.
   • dist[1][0] = 0.

2. Запустим Дейкстру по состояниям (время, вершина, потрачено) с приоритетной очередью.

3. Когда достаём состояние (curDist, v, spent):

   • если оно уже устарело, пропускаем;
   • перебираем все пешие тропы из v:
     • переходим в ту же сумму затрат spent;
   • перебираем все автобусные рейсы из v:
     • новая сумма затрат ns = spent + c;
     • если ns <= B, пробуем улучшить dist[to][ns].

4. После завершения алгоритма берём минимум среди всех dist[n][b].

5. Если минимум бесконечен, выводим -1, иначе выводим найденное время.

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

Рассмотрим расширенный граф состояний.

Его вершины — это пары (v, b), где:

• v — текущее место,
• b — уже потраченная сумма, 0 <= b <= B.

Рёбра в этом графе такие:

• для каждой пешей тропы u <-> v с весом w:

  • из (u, b) в (v, b) с весом w,
  • из (v, b) в (u, b) с весом w для каждого b;

• для каждого автобусного рейса u -> v с временем t и стоимостью c:

  • из (u, b) в (v, b + c) с весом t, если b + c <= B.

Тогда любой допустимый маршрут в исходной задаче однозначно соответствует пути в этом графе состояний:

• вершина показывает, где мы находимся;
• второй параметр показывает, сколько монет уже потрачено.

И наоборот, любой путь в графе состояний описывает допустимый маршрут в исходной задаче, потому что переходы точно повторяют правила перемещения.

Значит, задача сводится к поиску кратчайшего пути:

• из состояния (1, 0)
• в любое состояние (n, b), где 0 <= b <= B.

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

Следовательно, значения dist[v][b], найденные алгоритмом, действительно являются минимальными временами достижения места v при точной трате b монет. Тогда минимум по всем b от 0 до B и есть правильный ответ.

5. Сложность

Количество состояний:

• n * (B + 1)

Из каждого состояния рассматриваются:

• все пешие рёбра текущей вершины,
• все автобусные рёбра текущей вершины.

Итоговая оценка получается как Дейкстра по расширенному графу:

• по времени: O((n * B + (p + q) * B) * log(n * B))
• по памяти: O(n * B + p + q)

При B <= 1000 и данных ограничениях такое решение проходит.

6. Код на C++17

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

using namespace std;

struct WalkEdge {
    int to;
    int w;
};

struct BusEdge {
    int to;
    int t;
    int c;
};

int main() {
    int n, B;
    cin >> n >> B;

    vector<vector<WalkEdge>> walk(n + 1);
    vector<vector<BusEdge>> bus(n + 1);

    int p;
    cin >> p;
    for (int i = 0; i < p; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        walk[u].push_back({v, w});
        walk[v].push_back({u, w});
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u, v, t, c;
        cin >> u >> v >> t >> c;
        bus[u].push_back({v, t, c});
    }

    const long long INF = numeric_limits<long long>::max() / 4;

    vector<vector<long long>> dist(n + 1, vector<long long>(B + 1, INF));
    dist[1][0] = 0;

    using State = tuple<long long, int, int>;
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0LL, 1, 0});

    while (!pq.empty()) {
        auto [curDist, v, spent] = pq.top();
        pq.pop();

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

        for (const auto& e : walk[v]) {
            int to = e.to;
            long long nd = curDist + e.w;
            if (nd < dist[to][spent]) {
                dist[to][spent] = nd;
                pq.push({nd, to, spent});
            }
        }

        for (const auto& e : bus[v]) {
            int ns = spent + e.c;
            if (ns <= B) {
                int to = e.to;
                long long nd = curDist + e.t;
                if (nd < dist[to][ns]) {
                    dist[to][ns] = nd;
                    pq.push({nd, to, ns});
                }
            }
        }
    }

    long long ans = INF;
    for (int b = 0; b <= B; b++) {
        ans = min(ans, dist[n][b]);
    }

    if (ans == INF) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}

7. Код на Python 3

import heapq

n, B = map(int, input().split())

walk = [[] for _ in range(n + 1)]
bus = [[] for _ in range(n + 1)]

p = int(input())
for _ in range(p):
    u, v, w = map(int, input().split())
    walk[u].append((v, w))
    walk[v].append((u, w))

q = int(input())
for _ in range(q):
    u, v, t, c = map(int, input().split())
    bus[u].append((v, t, c))

INF = 10**30
dist = [[INF] * (B + 1) for _ in range(n + 1)]
dist[1][0] = 0

pq = [(0, 1, 0)]

while pq:
    cur_dist, v, spent = heapq.heappop(pq)
    if cur_dist != dist[v][spent]:
        continue

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

    for to, t, c in bus[v]:
        ns = spent + c
        if ns <= B:
            nd = cur_dist + t
            if nd < dist[to][ns]:
                dist[to][ns] = nd
                heapq.heappush(pq, (nd, to, ns))

ans = min(dist[n])
if ans >= INF:
    print(-1)
else:
    print(ans)