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.|

TOURS13 - VOI 2013 - Hành trình du lịch

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/tours13


Cô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 uj đến dịa diểm vj với chi phí đi lại là một số nguyên dương c(uj, vj). 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 xấu 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 uj, vj, c(uj, vj) cho biết thông tin về tuyến đường thứ j. Giả thiết là uj ≠ vj; c(uj, vj) < 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

Example

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

11

11

6

11

6

-1

Ràng buộc:

  • Có 30% số test tương ứng với 30% số điểm của bài có n <= 20.
  • Có 30% số test tương ứng với 30% số điểm của bài có 20 < n <= 100, m <= 104.
  • Có 40% số test tương ứng với 30% số điểm của bài có 100 < n <= 103, m <= 105

Được gửi lên bởi:VOJ Team
Ngày:2013-01-12
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:VOI 2013 - Ngày 2

hide comments
2013-12-04 13:02:14 Xiao Lang
@Thông: Dijkstra heap bình thường có điều cải tiến một chút trong cái Dijkstra đó là lúc đầu d[s]=0, sau khi nó chạy qua các đỉnh kề với s rồi thì cho d[s]=+oo thế là nó lại tự tìm lại đường đi đến đỉnh s và kết quả chính là d[s]. Có thể sử dụng cách tạo 1 cái đỉnh giả nhưng cách này dài khó code hơn cách trên.
2013-12-04 04:17:57 nguyenthethong1996
Ai có cách nào tốt không ạ? Bài em chỉ chạy được 60đ, dùng dijkstra tìm chu trình nhỏ nhất của từng đỉnh
2013-11-27 16:14:17 Xiao Lang
Có 2 người AC thì code bằng C++ hết... Time limited 1s có trụ nổi không nhỉ ?
2013-09-04 15:45:07 LOVE VNOI
Giới hạn T là bao nhiêu thế ạ :D :D :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.