Codeforces Beta Round 17 |
---|
Закончено |
В фирму Никиты набрали n человек. Теперь ему нужно построить древовидную иерархию отношений «начальник-подчинённый» в этой фирме (то есть у каждого человека, кроме одного, должен быть ровно один начальник). Дано m заявлений вида «человек ai готов стать начальником человека bi за дополнительную плату ci». Для каждого человека известно его значение квалификации qj, и для каждого заявления выполняется условие qai > qbi.
Помогите Никите определить минимальную стоимость создания иерархии, либо выяснить, что это невозможно.
В первой строке входных данных содержится целое число n (1 ≤ n ≤ 1000) — число сотрудников компании. В следующей строке содержится n чисел qj (0 ≤ qj ≤ 106) записанных через пробел — значения квалификации сотрудников. В следующей строке содержится число m (0 ≤ m ≤ 10000) — количество поданных заявлений. Следующие m строк содержат сами заявления, каждое из которых задаётся тремя числами, записанными через пробел: ai, bi и ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106). Заявления могут повторяться, то есть один и тот же сотрудник мог предложить стать начальником другому сотруднику за разные цены. Для каждого заявления qai > qbi.
В единственной строке выходных данных выведите минимальную стоимость создания иерархии или -1, если создать иерархию невозможно.
4
7 2 3 1
4
1 2 5
2 4 1
3 4 1
1 3 5
11
3
1 2 3
2
3 1 2
3 1 3
-1
В первом примере один из возможных вариантов составления иерархии — взять заявления под номерами 1, 2 и 4, которые в сумме дадут стоимость 11. Во втором примере составить иерархию невозможно, поэтому ответ -1.
Название |
---|