CHỌN ĐIỂM XÂY DỰNG (MS0039)MỘT VÙNG NÚI CÓ N ĐIỂM DÂN CỨ SINH SỐNG, CÁ...

Bài 2: Chọn điểm xây dựng (MS0039)Một vùng núi có N điểm dân cứ sinh sống, các điểm dân cư nằm ở độ cao từ 1 đến N. Từ hai điểm dâncư bất kỳ đều có đường đi đến với nhau. Để giải quyết nhu cầu nghiên cứu chống các bệnh do một loạiVirus là gây ra, lãnh đạo vùng quyết định đầu tư xây dựng một trung tâm nghiên cứu khoa học để nghiêncứu loại vi rút này và tác hại đến nó. Virus có thể gây tác hại trong một khoảng cách R. Khi nó gây tác hạiđến 1 địa điểm, mức độ gây thiệt hại của nó sẽ giảm đi bằng chính khoảng cách mà nó đã vượt qua. Trungtâm nghiên cứu được bảo vệ rất nghiêm ngặt. Một tên khủng bố đặt bom tại hàng rào của trung tâm làmcho virus bị phát tán. Ban lãnh đạo nhờ bạn tìm vị trí của trung tâm nghiên cứu sao cho nếu virus bị pháttán thì số điểm dân cư bị thiệt hại là ít nhất và điểm đặt trung tâm nghiên cứu phải có độ cao thấp nhất.Dữ liệu vào: File văn bản DIADIEM.INP+ Dòng đầu ghi hai số N và R (5<N≤700) và (0<R≤18000).+ Các dòng tiếp theo mỗi dòng ghi 3 số i, j và C với ý nghĩa khoảng cách từ điểm dân cư i đến j là C(0<C≤20000)Dữ liệu ra: ghi vào file văn bản DIADIEM.OUT chỉ có 1 số duy nhất ghi địa điểm trung tâm nghiêncứu

Ví dụ:

DIADIEM.INP DIADIEM.OUT7 355 1 2 201 7 302 3 302 5 303 4 303 5 403 7 704 5 605 6 606 7 20