Codeforces Round 918 (Div. 4) |
---|
Закончено |
Все друзья Славика планируют отправиться на вечеринку на своих велосипедах из места, где они живут. У всех есть велосипеды, кроме Славика. Есть $$$n$$$ городов, через которые они могут путешествовать. Все живут в городе $$$1$$$ и хотят пойти на вечеринку, которая находится в городе $$$n$$$. Карту городов можно рассматривать как ненаправленный граф с $$$n$$$ узлами и $$$m$$$ ребрами. Ребро $$$i$$$ соединяет города $$$u_i$$$ и $$$v_i$$$ и имеет длину $$$w_i$$$.
У Славика нет велосипеда, но у него есть деньги. В каждом городе есть ровно один велосипед, который можно купить. У велосипеда в $$$i$$$-м городе есть коэффициент медлительности $$$s_{i}$$$. Как только Славик купит велосипед, он может использовать его, чтобы путешествовать из города, в котором он находится, в любой город. Проезд по ребру $$$i$$$ с использованием велосипеда $$$j$$$ занимает время $$$w_i \cdot s_j$$$.
Славик может купить столько велосипедов, сколько захочет, так как деньги для него не проблема. Славик ненавидит путешествовать на велосипеде, поэтому он хочет добраться на вечеринку за минимальное время. И поскольку он уже подзабыл информатику, он просит вас ему помочь.
Какое минимальное количество времени потребуется Славику, чтобы добраться из города $$$1$$$ в город $$$n$$$? Славик не может путешествовать без велосипеда. Гарантируется, что возможно добраться от города $$$1$$$ до любого другого города.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следует описание самих наборов.
Первая строка каждого набора содержит два целых числа, разделенных пробелом: $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 1000$$$; $$$n - 1 \leq m \leq 1000$$$) — количество городов и количество дорог, соответственно.
$$$i$$$-я из следующих $$$m$$$ строк содержит три целых числа $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$; $$$1 \leq w_i \leq 10^5$$$), обозначающих, что есть дорога между городами $$$u_i$$$ и $$$v_i$$$ длиной $$$w_i$$$.
Следующая строка содержит $$$n$$$ целых чисел $$$s_1, \ldots, s_n$$$ ($$$1 \leq s_i \leq 1000$$$) — коэффициент медлительности каждого велосипеда. Одну и ту же пару городов может соединять больше, чем одна дорога.
Сумма $$$n$$$ по всем наборам не превышает $$$1000$$$, и сумма $$$m$$$ по всем наборам не превышает $$$1000$$$.
Дополнительное ограничение на ввод: возможно путешествовать от города $$$1$$$ до любого другого города.
Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество времени, за которое Славик может добраться из города $$$1$$$ в город $$$n$$$.
35 51 2 23 2 12 4 52 5 74 5 15 2 1 3 35 101 2 51 3 51 4 41 5 82 3 62 4 32 5 23 4 13 5 84 5 27 2 8 4 17 103 2 82 1 42 5 72 6 47 1 24 3 56 4 26 7 16 7 44 5 97 6 5 4 3 2 1
19 36 14
Название |
---|