crossings перекрёстков, пронумерованных от 0 до crossings - 1. Их соединяют двусторонние улицы: запись streets[i] = [a, b, t] значит, что по улице между перекрёстками a и b можно проехать за t минут в любую сторону. Между двумя перекрёстками не больше одной улицы, и из любого перекрёстка можно добраться до любого другого.
Курьер выезжает с перекрёстка 0 и хочет попасть на перекрёсток crossings - 1 как можно быстрее. Посчитайте, сколько существует разных маршрутов, которые занимают минимально возможное время. Маршруты различаются, если отличается последовательность пройденных перекрёстков.
Ответ может быть очень большим, поэтому верните его по модулю 10⁹ + 7.crossings=4, streets=[[0, 1, 3], [1, 3, 2], [0, 2, 1], [2, 3, 4], [1, 2, 2]] → 3
Быстрее всего добраться за 5 минут, и так получается тремя маршрутами: 0 → 1 → 3 (3 + 2), 0 → 2 → 3 (1 + 4) и 0 → 2 → 1 → 3 (1 + 2 + 2).
crossings=3, streets=[[0, 1, 4], [1, 2, 4], [0, 2, 9]] → 1
Через перекрёсток 1 дорога занимает 8 минут, напрямую — 9, поэтому самый быстрый маршрут один.
crossings=1, streets=[] → 1
Старт и финиш совпадают: ехать никуда не нужно, и это ровно один способ.
crossings ≤ 200crossings - 1 ≤ streets.length ≤ crossings · (crossings - 1) / 2streets[i] = [a, b, t], 0 ≤ a, b < crossings, a ≠ bt ≤ 10⁹crossings=4, streets=[[0, 1, 3], [1, 3, 2], [0, 2, 1], [2, 3, 4], [1, 2, 2]]
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 61 тест на сервере, включая скрытые.