Дешёвый перелёт с малым числом пересадок

Средняя

Есть cities городов с номерами от 0 до cities - 1 и список прямых рейсов flights: рейс [a, b, price] летит из города a в город b и стоит price. Нужно добраться из города origin в город destination, сделав не больше max_stops пересадок (промежуточных городов). Верните минимальную суммарную стоимость такого маршрута или -1, если добраться так нельзя.

Пример 1

cities=4, flights=[[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 300]], origin=0, destination=3, max_stops=1 → 100

Маршрут 0 → 2 → 1 → 3 стоит 80, но в нём две пересадки. С одной пересадкой лучший — 0 → 1 → 3 за 100.

Пример 2

cities=4, flights=[[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 300]], origin=0, destination=3, max_stops=2 → 80

Теперь две пересадки разрешены, и маршрут 0 → 2 → 1 → 3 за 80 подходит.

Пример 3

cities=3, flights=[[1, 0, 40]], origin=0, destination=2, max_stops=2 → -1

Из города 0 рейсов нет вообще.

Ограничения

1 ≤ cities ≤ 100
0 ≤ len(flights) ≤ cities·(cities − 1) / 2
flights[i] = [a, b, price], 0 ≤ a, b < cities, a ≠ b
1 ≤ price ≤ 10⁴
Между упорядоченной парой городов не больше одного рейса
0 ≤ origin, destination, max_stops < cities, origin ≠ destination

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Depth-First Search Breadth-First Search Graph Dynamic Programming Shortest Path Heap (Priority Queue)

Вход

cities=4, flights=[[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 300]], origin=0, destination=3, max_stops=1

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 92 теста на сервере, включая скрытые.