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
2020-06-27 13:31:56
Tham khảo:
Solution: http://megaurl.in/7cpQ
Code: http://m eg aurl. in/7 cp Q
2019-06-05 09:05:38
Dijktra with priority queue 1 đấm 90

Last edit: 2019-06-05 09:17:26
2018-12-25 14:03:36
Bài này mình dùng D'Esopo-Pape để tìm đường đi ngắn nhất được 98đ.
Các bạn có thể tham khảo tại đây: https://cp-algorithms.com/graph/desopo_pape.html
2018-11-29 10:37:28
Bài này làm sao cho tối ưu ta??


Last edit: 2018-11-29 10:37:53
2017-09-11 10:26:00
Các bạn nào muốn code thì inbox https://www.facebook.com/letrong.dat.31 mình cho code ...
2017-09-01 05:54:21
dijkstra heap nạp C++ 86, CPP 90 ảo thật :))
2017-08-06 11:02:01
Xem cách làm: https://vietcodes.github.io/code/33

Last edit: 2017-08-09 11:26:57
2017-05-28 07:38:44
from Dinh Truong Lam
floyd 70 còn dij là 88 nha ^^
2017-05-28 07:34:53
88 @@ sau 1 năm
2016-12-05 16:53:36 Nguyễn Hữu Phong
cài fibo heap thì may ra qua :'(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.