towns городов с номерами от 0 до towns - 1. Сначала есть только односторонние дороги из каждого города i в город i + 1.
По очереди открываются новые односторонние дороги: shortcuts[j] = [u, v] — дорога из города u в город v, причём u < v. Новая дорога может и дублировать уже существующую u → u + 1.
После открытия каждой дороги нужно узнать, за какое наименьшее число дорог можно доехать из города 0 в город towns - 1. Верните список этих чисел — по одному на каждую новую дорогу, в порядке открытия.towns=6, shortcuts=[[1, 4], [3, 5], [0, 3]] → [3, 3, 2]
После дороги 1 → 4 путь 0 → 1 → 4 → 5 занимает 3 дороги. Дорога 3 → 5 его не улучшает. После 0 → 3 получается 0 → 3 → 5 — 2 дороги.
towns=4, shortcuts=[[0, 3], [1, 3]] → [1, 1]
Первая же дорога ведёт прямо из 0 в 3, дальше ответ не меняется.
towns=6, shortcuts=[[1, 4], [3, 5], [0, 3]]
[3, 3, 2]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 67 тестов на сервере, включая скрытые.