| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P151PROD - ROUND 1D - Du hành giữa các vì sao |
Sau chuyến du hành giữa các vì sao nhóm Cooper tìm được hành tinh Edmunds phù hợp với sự sống ở thiên hà Blabla, anh đã gửi thông tin về cho con người ở Ngân Hà qua lỗ sâu. Vì di chuyển sang thiên hà Blabla tốn khá nhiều tài nguyên nên cần tập hợp tất cả người dân trên một trạm bất kì.
Có n trạm đang ở trên quỹ đạo của n hành tinh hay thiên thể khác nhau lân cận trong hệ mặt trời, mỗi hành tinh có d_i cư dân đang sinh sống, và có n-1 không gian 5 chiều để di chuyển trực tiếp giữa hai trạm và chỉ có một cách duy nhất để di chuyển giữa hai trạm bất kì. Mỗi không gian như vậy nối hai trạm u và v, để di chuyển 1 người từ trạm này sang trạm kia cần một lượng tài nguyên là w.
May thay các nhà khoa học đã nghiên cứu ra một cách chuyển đường đi trên qua một không gian nhiều chiều hơn, với cách đó việc di chuyển giữa hai trạm gần như không tốn tài nguyên, nhưng có một rắc rối là sự nhiễu trong không gian trên nên chỉ có thể chuyển tối đa k không gian cũ sang không gian mới.
Các nhà lãnh đạo đang tìm một cách di chuyển sao cho tốn ít tài nguyên nhất, bạn hãy giúp họ.
Input
Dòng đầu tiên chứa số bộ test, mỗi bộ test cấu trúc như sau:
- Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ n ≤ 1000, 0 ≤ k ≤ n − 1).
- Dòng thứ hai chứa n số tự nhiên, di là số dân đang sống trên trạm thứ i (1 ≤ d_i ≤ 100000).
- n-1 dòng còn lại, dòng thứ i chứa ba số nguyên dương ui, vi và wi (1 ≤ u_i, v_i ≤ n, 1 ≤ w_i ≤ 100000).
Output
In ra kết quả mỗi test trên một dòng.
Example
Input:1
5 3
8 5 1 8 7
1 3 8
2 3 9
3 5 7
3 4 8 Output: 45
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-04 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
