等级制度 (※※)
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
描述
尼克的公司有 n 个员工,每个员工 i有一个初始的权值 ,每一个员工有且只有一个上司。 有 m条申请,每个申请由三个数 ,,构成,代表将 任命为 的上司所需要的花费为,同时必须保证 (的权值必须大于的)。试求使每个员工(顶头上司除外)都有且只有一个上司所花费的最小代价。
你会帮助尼克计算这样一个层次结构的最小代价,若无解则输出-1。
输入格式
第一行 n,第二行 n 个数表示 ,第三行 m,之后 m 行每行三个数表示 ,,。
输出格式
一个整数表示最小代价,若无解则输出 -1
。
说明/提示
数据规模与约定
$1≤n≤10^3,0≤m≤10^4, 0≤q_i≤10^6,0≤c_i≤10^6,1≤a_i,b_i≤n$ 。
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:1成为2和3的上司,花费10,2成为4或3成为4的上司,花费1,共花费11。
样例2:2和其他没有申请所以没有解,输出-1。