VOI 13 Bài 5 - Hành trình du lịch
Xem dạng PDFCông ty du lịch ~X~ có dự án tổ chức các hành trình du lịch trong vùng lãnh thổ gồm ~n~ điểm du lịch trọng điểm, được đánh số từ ~1~ tới ~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~, ~3~, ..., ~m~) cho phép đi từ địa diểm ~u_{j}~ đến dịa diểm ~v_{j}~ với chi phí đi lại là một số nguyên dương ~c~(~u_{j}~, ~v_{j}~). Vấn đề đặt ra cho công ty là xây dựng các hành trình du lịch cho mỗi điểm du lịch. Một hành trình du lịch cho địa điểm du lịch ~i~ phải được xây dựng sao cho xuất phát từ địa điểm ~i~ đi qua một số địa điểm khác rồi quay lại địa điểm xuất phát ~i~ với tổng chi phí (được tính như là tổng chi phí của các tuyến đường mà hành trình đi qua) nhỏ nhất.
Input
Dòng đầu tiên số ~T~ là số lượng bộ dữ liệu. Tiếp đến là ~T~ nhóm dòng, mỗi dòng cho thông tin về một bộ dữ liệu theo khuôn dạng sau:
- Dòng thứ nhất chứa ~2~ số nguyên dương ~n~, ~m~
- Dòng thứ ~j~ trong số ~m~ dòng tiếp theo chứa ba số nguyên duong ~u_{j}~, ~v_{j}~, ~c~(~u_{j}~, ~v_{j}~) cho biết thông tin về tuyến đường thứ ~j~. Giả thiết là ~u_{j} \neq v_{j}~; ~c~(~u_{j}~, ~v_{j}~) ~< 10^{6}~; ~j = 1~, ~2~, ..., ~m~
Output
Gồm ~T~ nhóm dòng tương ứng với ~T~ bộ test vào, mỗi nhóm dòng gồm ~n~ dòng, dòng thứ ~i~ ghi chi phí của hành trình du lịch cho địa điểm ~i~.
Qui ước: Ghi số ~-1~ trên dòng ~i~ nếu không tìm được hành trình du lịch cho địa điểm ~i~ thỏa mãn yêu cầu đặt ra
Giới hạn
Ràng buộc:
- Có 30% số test tương ứng với 30% số điểm của bài có ~n \le 20~.
- Có 30% số test tương ứng với 30% số điểm của bài có ~20 < n \le 100~, ~m \le 10^{4}~.
- Có 40% số test tương ứng với 30% số điểm của bài có ~100 < n \le 10^{3}~, ~m \le 10^{5}~
Sample Input
1
6 8
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7
Sample Output
11
11
6
11
6
-1
Bình luận
bài này e có chạy trâu bằng cách dijkstra từ mọi đỉnh nhưng bị tle mất 2 test, có cách nào tối ưu không hay phải đổi thuật toán vậy mn
mình nghĩ là floyd gì đó vợi độ phúc tạp O(n^2) gì đó bạn
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.