1. Идея

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

Если прийти в одну и ту же вершину разными способами, то ситуация может отличаться количеством потраченных купонов. Например, оказаться в магазине v с ценой 10 и 0 использованными купонами — это не то же самое, что оказаться там же с ценой 10, но уже с k использованными купонами. Во втором случае возможностей дальше меньше.

Поэтому будем искать кратчайшие расстояния не просто до вершины, а до состояния (вершина, использовано_купонов).

Тогда из состояния (v, used) по ребру веса w можно сделать два перехода:

• поехать без купона: перейти в (to, used) с добавлением стоимости w;
• если used < k, применить купон: перейти в (to, used + 1) с добавлением стоимости 0.

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

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

Наблюдение 1

Купоны не обязательно использовать все. В условии сказано: можно использовать не более k купонов.

Значит, ответ — это минимум среди всех dist[n][used], где used от 0 до k.

Наблюдение 2

Все стоимости переходов неотрицательны:

• обычный проезд стоит w >= 0;
• проезд по купону стоит 0.

Значит, алгоритм Дейкстры применим.

Наблюдение 3

Можно представить задачу как многослойный граф:

• слой 0 — купонов использовано 0,
• слой 1 — купонов использовано 1,
• ...
• слой k — купонов использовано k.

Для каждого ребра u - v веса w:

• внутри одного слоя есть переходы стоимости w;
• из слоя used в слой used + 1 есть переходы стоимости 0, если используем купон.

Но строить этот граф явно не обязательно. Достаточно хранить dist[v][used] и генерировать переходы на лету.

3. Алгоритм

1. Считываем граф.
2. Создаём массив dist, где dist[v][used] — минимальная стоимость добраться до вершины v, использовав ровно used купонов.
3. Изначально:
   • dist[1][0] = 0,
   • все остальные значения равны бесконечности.
4. Помещаем в приоритетную очередь состояние (0, 1, 0).
5. Пока очередь не пуста:
   • достаём состояние с минимальной стоимостью: (curDist, v, used);
   • если это устаревшая запись, пропускаем;
   • для каждого ребра v -> to веса w:
     • пробуем перейти без купона:
       • если curDist + w лучше, обновляем dist[to][used];
     • пробуем перейти с купоном:
       • если used < k и curDist лучше, обновляем dist[to][used + 1].
6. После завершения берём минимум среди dist[n][0], dist[n][1], ..., dist[n][k].
7. Если все эти значения бесконечны, выводим -1, иначе выводим найденный минимум.

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

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

Какие состояния мы рассматриваем

Каждое состояние задаётся парой (v, used):

• v — текущий магазин,
• used — сколько купонов уже потрачено.

Это полностью описывает всё, что важно для дальнейшего движения:

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

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

Какие переходы есть между состояниями

Если из вершины v есть ребро в to стоимости w, то:

• можно пройти его обычно и перейти в (to, used) за цену w;
• если купоны ещё остались, можно пройти его бесплатно и перейти в (to, used + 1) за цену 0.

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

Почему Дейкстра подходит

Все веса переходов в графе состояний неотрицательны: это либо w >= 0, либо 0. Значит, на таком графе корректно работает алгоритм Дейкстры.

Следовательно, после завершения алгоритма dist[v][used] будет равен минимальной стоимости попасть в магазин v, использовав ровно used купонов.

Почему ответ — минимум по всем used

По условию разрешено использовать не более k купонов, а не ровно k. Значит, конечное состояние может иметь любое число использованных купонов от 0 до k.

Поэтому правильный ответ:

• минимум среди всех dist[n][used], где 0 <= used <= k.

Если ни одно из этих состояний недостижимо, то добраться до магазина n невозможно, и нужно вывести -1.

5. Сложность

Пусть в графе n вершин и m рёбер.

Состояний будет n * (k + 1).

Из каждого состояния мы рассматриваем все исходящие рёбра, значит общее число переходов порядка m * (k + 1).

Итоговая сложность Дейкстры:

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

При данных ограничениях это проходит:

• k <= 50, так что дополнительный множитель по купонам невелик.

6. Код на C++17

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

using namespace std;

struct Edge {
    int to;
    long long w;
};

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

    vector<vector<Edge>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long 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<vector<long long>> dist(n + 1, vector<long long>(k + 1, INF));
    priority_queue<
        tuple<long long, int, int>,
        vector<tuple<long long, int, int>>,
        greater<tuple<long long, int, int>>
    > pq;

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

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

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

        for (const Edge &e : g[v]) {
            int to = e.to;
            long long w = e.w;

            if (dist[to][used] > curDist + w) {
                dist[to][used] = curDist + w;
                pq.push({dist[to][used], to, used});
            }

            if (used < k && dist[to][used + 1] > curDist) {
                dist[to][used + 1] = curDist;
                pq.push({dist[to][used + 1], to, used + 1});
            }
        }
    }

    long long ans = INF;
    for (int used = 0; used <= k; used++) {
        if (dist[n][used] < ans) {
            ans = dist[n][used];
        }
    }

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

    return 0;
}

7. Код на Python 3

import heapq

n, m, k = 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] * (k + 1) for _ in range(n + 1)]

dist[1][0] = 0
pq = [(0, 1, 0)]

while pq:
    cur_dist, v, used = heapq.heappop(pq)

    if cur_dist != dist[v][used]:
        continue

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

        if used < k and cur_dist < dist[to][used + 1]:
            dist[to][used + 1] = cur_dist
            heapq.heappush(pq, (cur_dist, to, used + 1))

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