Задачи 8 / 9 — Мин. стоимость пути s→t с не более чем K пересадками
Граф авиаперелётов: ребро (u, v, c) — перелёт стоимостью c > 0. Найти минимальную стоимость пути из s в t, используя не более K пересадок (то есть ≤ K+1 рёбер). Задача 8 — частный случай c ∈ {1,2}.
Идея. Это Беллман-Форд с ограничением на число рёбер. dp[k][v] = мин. стоимость добраться до v, использовав ≤ k рёбер. Делаем ровно K+1 раундов релаксации всех рёбер по «слоям». Обычная Дейкстра не годится — она не контролирует число рёбер.