Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PVOI14_3 - TOUR

Sau khi xây dựng xong khu du lịch, thầy Minh bắt tay vào khai thá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 1 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 một 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ề địa đ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 là nhỏ nhất.

Input

  • Dòng thứ nhất chứa 2 số nguyên dương N ≤ 103, M ≤ 104
  • Dòng thứ j trong số M dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c_j cho biết thông tin về tuyến đường thứ j. Giả thết là u_j khác v_j; c_j <= 109 với j = 1, 2, ..., M.

Output

Ghi ra giá trị tổng chi phí cho số địa điểm trên hành trình tìm được, làm tròn tới đúng 2 chữ số sau dấu phẩy. 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.

Example

Input:
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

Output:
2.00

 

Input:
2 1
1 2 3
Output:
NO TOUR

Được gửi lên bởi:VOJ Team
Ngày:2014-12-15
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:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:PreVOI 2014

hide comments
2018-09-13 15:03:28
Ai cần test AC liên hệ canh.manh135@gmail.com nha

Last edit: 2018-09-13 15:04:36
2018-01-01 15:32:35
đề troll nhiều tuyến 1 chiều cho bác nào 90-95 :)))
2018-01-01 15:06:49
90 lỗi gì thế mấy bác :'(((
2017-08-17 15:48:24
Solution và code mẫu có thể tham khảo tại : http://cowboycoder.tech/spoj/spoj-pvoi14_3-tour
2016-11-29 11:13:13 Lương Ðức Tuấn Ðạt
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://YeuLapTrinh.PW/426/pvoi14_3-spoj/

Last edit: 2016-11-29 11:14:16
2016-07-09 22:08:31
Sol chuẩn độ phức tạp O(nm + n ^ 2)

Last edit: 2016-07-09 22:09:22
2015-12-05 00:58:21 ChienTran
O(n*m*logm), cube khỏe vl
2015-08-06 10:29:45 Prismatic
Phiên bản EASY của QBTRANS
2014-12-25 14:29:13 Nắng
Cube khỏe vãi
2014-12-25 12:46:24 never give up !!
60 :((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.