n интересных мест, пронумерованных от 0 до n − 1; в месте 0 стоит ваша гостиница. Красота места i — beauty[i]. Места соединены двусторонними дорогами: roads[j] = [u, v, t] означает, что путь между u и v в любую сторону занимает t минут.
Прогулка начинается и заканчивается в гостинице и длится не больше time_limit минут. По дорогам и местам можно проходить сколько угодно раз, но красота каждого посещённого места засчитывается **один раз**. Гостиница тоже считается посещённой.
Верните наибольшую суммарную красоту, которую может собрать такая прогулка.beauty=[3, 20, 7, 12], roads=[[0, 1, 15], [1, 2, 10], [0, 2, 25], [0, 3, 30]], time_limit=50 → 30
Маршрут 0 → 1 → 2 → 0 занимает 15 + 10 + 25 = 50 минут и собирает 3 + 20 + 7 = 30. Место 3 даёт больше красоты, но туда и обратно — 60 минут.
beauty=[1, 50, 9], roads=[[0, 2, 10], [1, 2, 40]], time_limit=40 → 10
До места 1 не успеть вернуться, зато 0 → 2 → 0 за 20 минут даёт 1 + 9 = 10.
beauty=[4, 6], roads=[], time_limit=10 → 4
Дорог нет: можно лишь остаться у гостиницы, это красота 4.
beauty=[3, 20, 7, 12], roads=[[0, 1, 15], [1, 2, 10], [0, 2, 25], [0, 3, 30]], time_limit=50
30
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 69 тестов на сервере, включая скрытые.