n городов, пронумерованных от 1 до n. Дороги двусторонние: roads[i] = [a, b, cost] — дорога между городами a и b, проезд по ней стоит cost.
В каждом городе продаётся сувенир; в городе i он стоит prices[i - 1].
Вы выезжаете из своего города, добираетесь по дорогам до любого города (можно остаться в своём), покупаете там ровно один сувенир и возвращаетесь домой. На обратном пути вы везёте покупку, поэтому каждая дорога обходится в k раз дороже обычного.
Верните массив длины n, где i-й элемент (с нуля) — минимальная полная стоимость поездки за сувениром для того, кто живёт в городе i + 1. Граф может быть несвязным.n=3, roads=[[1, 2, 3], [2, 3, 10]], prices=[20, 9, 4], k=2 → [18, 9, 4]
Из города 1: съездить в город 2 (3), купить за 9 и вернуться (3 · 2 = 6) — итого 18, дешевле, чем 20 на месте. Город 2 покупает у себя за 9. Город 3 покупает у себя за 4.
n=2, roads=[[1, 2, 1]], prices=[50, 10], k=1 → [12, 10]
Из города 1 выгодно съездить в город 2: 1 + 10 + 1 = 12.
n=4, roads=[[1, 2, 5], [3, 4, 1]], prices=[7, 30, 30, 2], k=3 → [7, 27, 6, 2]
n=3, roads=[[1, 2, 3], [2, 3, 10]], prices=[20, 9, 4], k=2
[18, 9, 4]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 72 теста на сервере, включая скрытые.