n перекрёстков, пронумерованных от 1 до n. Они соединены двусторонними дорогами: roads[i] = [u, v, w] означает дорогу длины w между перекрёстками u и v. Из любого перекрёстка можно добраться до любого другого.
На перекрёстке n стоит склад. Для каждого перекрёстка x обозначим через d(x) длину кратчайшего пути от x до склада.
Курьер выезжает с перекрёстка 1 и хочет доехать до склада, но с причудой: после каждого переезда по дороге он должен оказаться строго ближе к складу, чем был. То есть маршрут x₀ = 1, x₁, ..., x_k = n подходит, если d(xᵢ) > d(xᵢ₊₁) для каждого шага.
Посчитайте, сколько существует таких маршрутов. Ответ может быть очень большим, поэтому верните его по модулю 10⁹ + 7.n=4, roads=[[1, 2, 2], [2, 4, 1], [1, 3, 1], [3, 4, 3], [2, 3, 1]] → 3
Кратчайшие расстояния до склада 4: у перекрёстка 2 — 1, у 3 — 2, у 1 — 3. Подходят маршруты 1 → 2 → 4, 1 → 3 → 4 и 1 → 3 → 2 → 4: на каждом шаге расстояние до склада строго уменьшается.
n=3, roads=[[1, 2, 1], [2, 3, 1], [1, 3, 5]] → 2
Расстояния: у 2 — 1, у 1 — 2. Можно ехать напрямую 1 → 3 или через 2, итого 2 маршрута.
n=2, roads=[[1, 2, 7]] → 1
n=4, roads=[[1, 2, 2], [2, 4, 1], [1, 3, 1], [3, 4, 3], [2, 3, 1]]
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 42 теста на сервере, включая скрытые.