Есть n счетов, номера от 0 до n − 1. Канал [u, v, fee] разрешает перевод со счёта u на счёт v с комиссией fee рублей; в обратную сторону — только отдельным каналом.
Деньги нужно довести со счёта src до счёта dst. У клиента один промокод: он обнуляет комиссию одного любого перевода в цепочке. Верните минимальную сумму комиссий или -1, если до dst не добраться.
В работе: Подбор маршрута перевода между своими счетами и картами других банков, когда на месяц выдан один бесплатный перевод.
Пример 1
n = 4 channels = [[0, 1, 100], [1, 3, 100], [0, 2, 30], [2, 3, 150]] src = 0 dst = 3
30
Без промокода дешевле 0 → 1 → 3 (200), но с промокодом выгоднее 0 → 2 → 3: 30 + 0 = 30.
Пример 2
n = 3 channels = [[0, 1, 50]] src = 0 dst = 2
-1
До счёта 2 каналов нет.
Ограничения
- 1 ≤ n ≤ 10⁵
- 0 ≤ число каналов ≤ 4·10⁵
- 0 ≤ fee ≤ 10⁴
- Лимит — 3 с на тест (3000 мс).
print() и console.log() уходят в консоль.
def cheapest_with_coupon(n, channels, src, dst):
Источник: наша задача на данных Т-Банка. Условие пересказано своими словами.
Ожидаемый ответ не нужен: покажем, что вернула функция.
Здесь появится результат отправки.