Hệ thống cấp bậc

Điểm: 4,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một công ty có $n$ nhân viên. Cần xây dựng một cây cấp bậc kiểu "cấp trên – cấp dưới": mỗi nhân viên, ngoại trừ đúng một người (người đứng đầu), có đúng một cấp trên.

Có $m$ đơn đăng ký, mỗi đơn có dạng: "nhân viên $a_{i}$ sẵn sàng làm cấp trên của nhân viên $b_{i}$ với chi phí phụ trội $c_{i}$ ". Mỗi nhân viên $j$ có một chỉ số năng lực $q_{j}$ đã biết, và mọi đơn đều thoả mãn $q_{a_{i}} > q_{b_{i}}$ .

Hãy tính tổng chi phí nhỏ nhất để xây dựng cây cấp bậc như vậy, hoặc khẳng định không thể.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số nhân viên.
Dòng thứ hai chứa $n$ số nguyên $q_{1}, q_{2}, \dots, q_{n}$ — năng lực của các nhân viên.
Dòng thứ ba chứa số nguyên $m$ — số đơn đăng ký.
$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_{i}$ , $b_{i}$ , $c_{i}$ — đơn đăng ký. Hai đơn khác nhau có thể trùng cặp $(a, b)$ nhưng khác $c$ .

Dữ liệu ra

In ra một số nguyên duy nhất — tổng chi phí nhỏ nhất để xây cây cấp bậc, hoặc $- 1$ nếu không thể.

Ràng buộc

$1 \leq n \leq 1000$
$0 \leq q_{j} \leq 10^{6}$
$0 \leq m \leq 10000$
$1 \leq a_{i}, b_{i} \leq n$ , $0 \leq c_{i} \leq 10^{6}$
$q_{a_{i}} > q_{b_{i}}$ với mọi đơn $i$ .

Ví dụ

Input	Output	Giải thích
4 7 2 3 1 4 1 2 5 2 4 1 3 4 1 1 3 5	11	Chọn đơn 1 ( $1 \to 2$ , chi phí 5), đơn 2 ( $2 \to 4$ , chi phí 1) và đơn 4 ( $1 \to 3$ , chi phí 5). Nhân viên 1 là gốc; tổng chi phí $5 + 1 + 5 = 11$ .
3 1 2 3 2 3 1 2 3 1 3	-1	Cả nhân viên 2 và 3 đều không có ai có thể làm cấp trên (không có đơn nào nhắm vào họ), nên không thể tạo cây cấp bậc với đúng một gốc.

Bình luận

Không có bình luận tại thời điểm này.