HÀNH TRÌNH DU LỊCH

Nguồn: PreVOI2014-2015
Sau khi xây dựng xong khu du lịch, thầy Minh bắt tay vào khai tác bằng cách tổ chức các hành trình du lịch. Khu du lịch gồm n địa điểm đánh số từ 1 đến n. Hệ thông giao thông trong vùng gồm m tuyến đường một chiều khác nhau, tuyến đường thứ j (j=1,2,…,m) cho phép đi từ địa điểm u_j đến địa điểm v_j với chi phí đi lại là số nguyên dương c_j. Công ty vừa nhận được hợp đồng yêu cầu xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch bất kỳ và đi thăm một số địa điểm du lịch sau đó quay về điểm xuất phát mà chi phí trung bình là nhỏ nhất. Chi phí trung bình được tính bằng tổng chi phí của các tuyến đường mà hành trình đi qua chia cho số tuyến đường trên hành trình.

Yêu cầu: Cho thông tin về hệ thống giao thông, hãy xây dựng một hành trình du lịch với chi phí trung bình nhỏ nhất.

Dữ liệu vào: Từ tệp văn bản TOUR.INP

+ Dòng đầu tiên chứa hai số nguyên dương n<=10³ và m<=10⁴

+ Dòng thứ j trong số m dòng tiếp theo chứa 3 số nguyên u_j, v_j, c_j cho biết thông tin về tuyến đường thứ j. Giải thiết u_j≠v_j; c_j<=10⁹ với j=1,2,…,m.

Kết quả: ghi ra tệp văn bản TOUR.OUT giá trị tổng chi phí chia cho số địa điểm trên hành trình tìm được làm tròn đến 2 chữ số sau dấu chấm thập phân. Ghi ra xâu NO TOUR nếu không tìm được hành trình du lịch thỏa mãn yêu cầu.

Ví dụ:

TOUR.INP	TOUR.OUT
6 8 1 2 4 2 4 1 4 3 3 3 1 4 4 1 1 3 5 5 5 3 1 5 6 7	2.00
2 1 1 2 3	NO TOUR

Giới hạn:

25% số điểm có N<=10

25% số điểm có N<=20

25% số điểm có N<=100

25% số điểm có N<=1000

Thuật toán KARP TEST CODE

+++++++++++++++++++++
+    TRẦN THIỆN DINH    +
+    Chuyên Tin 2013-2016  +
+ Lê Quý Đôn - Khánh Hòa +
+++++++++++++++++++++