Bài toán Di chuyển nhanh nhất

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Trong một vùng sinh thái có n hòn đảo đánh số từ 1 đến n. Ở k hòn đảo trong số này có các khu nhà dành cho khách du lịch. Các đảo được nối với nhau bởi đúng n1 cây cầu sao cho mọi đảo đều đi đến được với nhau. Với mỗi cây cầu, đều xác định được thời gian để một chiếc ô tô tải đi hết của nó (từ đảo này sang đảo kia). Hàng ngày Nam phải chuyển thực phẩm đến k khu nhà nghỉ bằng cách từ đất liền cập bến một đảo nào đó, sau đó dùng xe tải xuất phát từ đảo này đi hết tất cả k hòn đảo có khu nhà nghỉ. Anh ta dừng lại tại hòn đảo cuối cùng trong số k hòn đảo có nhà nghỉ và từ đây đi tàu thủy về đất liền. Nam muốn xác định với mỗi hòn đảo dùng làm nơi xuất phát thì tổng quãng đường lái xe tải tối thiểu là bao nhiêu?

Dữ liệu:

  • Dòng đầu tiên ghi hai số nguyên n,k (1<n5.105,1<k<n)</li>
  • n1 dòng tiếp theo, mỗi dòng chứa ba số nguyên A,B,C (1A,B𝑁,1C106) thể hiện có một cầu nối đảo A với đảo B có độ dài C.
  • k dòng cuối cùng, mỗi dòng ghi chỉ số của một hòn đảo có nhà nghỉ

Kết quả:

Gồm n dòng, dòng thứ i ghi quãng đường ngắn nhất mà Nam phải lái xe nếu như xuất phát từ đảo thứ i.

Ví dụ:
Input
Copy
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5
Output
Copy
5
3
7
2
2

Ràng buộc:

  • Có 40% số test tương ứng 40% số điểm có 𝑁1000
  • Có 20% số test tương ứng 20% số điểm có 1000<𝑁<105
  • 40% số test còn lại tương ứng 40% số điểm có 105𝑁<5.105

Comments

Please read the guidelines before commenting.


There are no comments at the moment.