1. Идея

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

Поэтому будем строить неявный граф состояний:

• состояние — это пара (город, остаток топлива);
• из состояния (v, fuel) можно поехать по дороге v -> to веса w, если fuel >= w;
• после переезда:
  • если в городе to есть заправка, то бак сразу становится полным: C;
  • иначе остаётся fuel - w.

Цена такого перехода равна w, потому что именно столько топлива тратится на эту дорогу.

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

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

Наблюдение 1. Нужно хранить остаток топлива

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

Например:

• в одном случае топлива хватает до следующей важной дороги;
• в другом — уже нет.

Значит, вершины вида просто dist[v] недостаточно. Нужны состояния dist[v][fuel].

Наблюдение 2. Заправка не увеличивает ответ

По условию автоматическая заправка ничего не стоит. Она только меняет состояние бака.

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

Наблюдение 3. Стартовое состояние одно

В начале водитель находится в городе s с полным баком, значит старт — это состояние (s, C) с расстоянием 0.

Наблюдение 4. Финишных состояний несколько

В город t можно приехать с любым остатком топлива от 0 до C. Поэтому ответ — минимум среди всех dist[t][fuel].

3. Алгоритм

Будем хранить граф дорог списками смежности.

Создадим массив has_refuel, где has_refuel[v] = 1, если в городе v есть заправка.

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

Представление состояния

Удобно считать, что у каждого города есть C + 1 возможных остатков топлива: от 0 до C.

Тогда состояние (city, fuel) можно закодировать одним числом:

• id = city * (C + 1) + fuel

Это позволяет хранить все расстояния в одномерном массиве.

Переходы

Пусть из очереди извлекли состояние (v, fuel) с текущей стоимостью cur_dist.

Для каждой дороги (v, to, w):

• если fuel < w, проехать нельзя;
• иначе:
  • если to — город с заправкой, то new_fuel = C;
  • иначе new_fuel = fuel - w;
  • новая стоимость nd = cur_dist + w.

Если nd лучше текущего расстояния до состояния (to, new_fuel), обновляем его и кладём в очередь.

Завершение

После окончания Дейкстры берём минимум по всем состояниям (t, fuel).

Если все они недостижимы, выводим -1.

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

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

1. Граф состояний корректно описывает все допустимые маршруты

Каждый реальный маршрут водителя можно разбить на последовательность шагов по дорогам.

После каждого шага важно знать:

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

Именно это и задаёт состояние (город, топливо).

Переходы между такими состояниями в точности соответствуют допустимым поездкам по дорогам:

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

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

2. Любой путь в графе состояний соответствует допустимому маршруту

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

Значит, этот путь соответствует реальному маршруту грузовика.

3. Стоимость пути совпадает с суммарным расходом топлива

Вес каждого перехода равен w — количеству топлива, которое нужно на соответствующую дорогу.

Автоматическая заправка не добавляет стоимость.

Следовательно, сумма весов переходов в графе состояний точно равна суммарному расходу топлива на маршруте.

4. Дейкстра применима

Все веса переходов неотрицательны, потому что w >= 1.

Значит, на графе состояний можно применять алгоритм Дейкстры, и он найдёт кратчайшие расстояния от стартового состояния (s, C) до всех остальных состояний.

5. Почему ответ — минимум по всем остаткам топлива в городе t

Задача требует только добраться до города t. Сколько топлива останется в баке в конце, неважно.

Поэтому среди всех состояний (t, 0), (t, 1), ..., (t, C) нужно выбрать минимальное расстояние.

Именно это и делает алгоритм.

5. Сложность

Пусть число состояний равно n * (C + 1).

• Вершин в графе состояний: O(nC)
• Из каждого состояния рассматриваются все дороги исходного города, поэтому переходов в сумме порядка O(mC)

Алгоритм Дейкстры работает за:

• O((nC + mC) log(nC))

То есть можно записать как:

• O(C * (n + m) * log(nC))

Память:

• O(nC + m)

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

6. Код на C++17

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

using namespace std;

struct Edge {
    int to;
    int w;
};

int main() {
    int n, m, C;
    cin >> n >> m >> C;

    int s, t;
    cin >> s >> t;

    int r;
    cin >> r;
    vector<int> has_refuel(n + 1, 0);
    for (int i = 0; i < r; i++) {
        int x;
        cin >> x;
        has_refuel[x] = 1;
    }

    vector<vector<Edge>> 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;
    int states_per_city = C + 1;
    long long total_states = 1LL * (n + 1) * states_per_city;
    vector<long long> dist(total_states, INF);

    auto id = [states_per_city](int city, int fuel) -> long long {
        return 1LL * city * states_per_city + fuel;
    };

    priority_queue<
        tuple<long long, int, int>,
        vector<tuple<long long, int, int>>,
        greater<tuple<long long, int, int>>
    > pq;

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

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

        long long cur_id = id(v, fuel);
        if (cur_dist != dist[cur_id]) {
            continue;
        }

        for (const Edge &e : g[v]) {
            if (fuel < e.w) {
                continue;
            }

            int new_fuel;
            if (has_refuel[e.to]) {
                new_fuel = C;
            } else {
                new_fuel = fuel - e.w;
            }

            long long nd = cur_dist + e.w;
            long long nid = id(e.to, new_fuel);

            if (nd < dist[nid]) {
                dist[nid] = nd;
                pq.push({nd, e.to, new_fuel});
            }
        }
    }

    long long ans = INF;
    for (int fuel = 0; fuel <= C; fuel++) {
        long long cur = dist[id(t, fuel)];
        if (cur < ans) {
            ans = cur;
        }
    }

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

    return 0;
}

7. Код на Python 3

import heapq

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

tmp = list(map(int, input().split()))
r = tmp[0]
has_refuel = [False] * (n + 1)
for x in tmp[1:]:
    has_refuel[x] = True

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
states_per_city = C + 1
dist = [INF] * ((n + 1) * states_per_city)

def get_id(city, fuel):
    return city * states_per_city + fuel

start_id = get_id(s, C)
dist[start_id] = 0
pq = [(0, s, C)]

while pq:
    cur_dist, v, fuel = heapq.heappop(pq)
    cur_id = get_id(v, fuel)

    if cur_dist != dist[cur_id]:
        continue

    for to, w in g[v]:
        if fuel < w:
            continue

        if has_refuel[to]:
            new_fuel = C
        else:
            new_fuel = fuel - w

        nd = cur_dist + w
        nid = get_id(to, new_fuel)

        if nd < dist[nid]:
            dist[nid] = nd
            heapq.heappush(pq, (nd, to, new_fuel))

ans = min(dist[get_id(t, fuel)] for fuel in range(C + 1))
print(-1 if ans == INF else ans)