Codeforces Round 857 (Div. 1) |
---|
Закончено |
Добираться он собирается самолетами. Всего в стране есть $$$m$$$ авиарейсов, $$$i$$$-й летит из города $$$a_i$$$ в город $$$b_i$$$ и стоит $$$s_i$$$ монет. Обратите внимание, что $$$i$$$-й рейс односторонний, то есть не может использоваться, чтобы добраться из города $$$b_i$$$ в город $$$a_i$$$. Чтобы им воспользоваться, Боря должен быть в городе $$$a_i$$$ и иметь на руках хотя бы $$$s_i$$$ монет (которые он потратит на перелет).
После ограбления у него осталось всего $$$p$$$ монет, однако он не отчаивается! Находясь в городе $$$i$$$, он может хоть каждый день организовывать представления, которые будут приносить ему по $$$w_i$$$ монет каждый.
Помогите фокуснику узнать, сможет ли он добраться до дома, а также какое минимальное количество представлений придется для этого организовать.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 80$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных содержит три целых числа $$$n$$$, $$$m$$$ и $$$p$$$ ($$$2 \le n \le 800$$$, $$$1 \le m \le 3000$$$, $$$0 \le p \le 10^9$$$) — количество городов, количество авиарейсов и изначальное количество монет.
Во второй строке каждого набора входных даны $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ $$$(1 \le w_i \le 10^9)$$$ — прибыль от представлений.
В следующих $$$m$$$ строках даны по три целых числа $$$a_i$$$, $$$b_i$$$ и $$$s_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$1 \le s_i \le 10^9$$$) — начальный и конечный город, а также стоимость $$$i$$$-го авиарейса.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$800$$$, а также, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10000$$$.
Для каждого теста выведите единственное целое число — минимальное количество представлений, которое придется организовать Боре, чтобы добраться до дома, или $$$-1$$$, если это сделать невозможно.
44 4 27 4 3 11 2 213 2 61 3 82 4 114 4 101 2 10 11 2 202 4 301 3 253 4 894 4 75 1 6 21 2 52 3 103 4 503 4 704 1 21 1 1 11 3 2
4 24 10 -1
В первом примере Боре оптимально сделать $$$4$$$ представления в первом городе, имея в итоге $$$2 + 7 \cdot 4 = 30$$$ рублей, а потом пройтись по маршруту $$$1-3-2-4$$$, потратив $$$6+8+11=25$$$ рублей.
Во втором примере Боре оптимально сделать $$$15$$$ представлений в первом городе, полететь в $$$3$$$ город, сделать там $$$9$$$ представлений, и далее отправиться в $$$4$$$ город.
Название |
---|