TRAFFICN - Traffic Network


Mạng lưới giao thông thành phố gồm n nút được đánh số từ 1 đến n và m đường một chiều nối các cặp nút. Để giảm được độ dài của đường đi ngắn nhất giữa hai nút trọng yếu s và t khác nhau, một danh sách gồm k đường hai chiều được đề xuất để xem xét xây dựng.

Nhiệm vụ của bạn là viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất giữa s và t là nhỏ nhất.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa năm số nguyên dương n (n ≤ 10 000), m (m ≤ 100 000), k (k < 300), s (1 ≤ s ≤ n), t (1 ≤ t ≤ n) cách nhau bởi dấu trống. Dòng thứ i trong m dòng tiếp theo chứa ba số nguyên dương di, ci, li cách nhau bởi dấu trống, trong đó li là độ dài ( 0< li ≤ 1000) của đường một chiều thứ i từ nút di đến nút ci. Dòng thứ j trong k dòng tiếp theo chứa ba số nguyên dương uj, vj và qj (qj ≤ 1000) cách nhau bởi dấu trống, trong đó qj là độ dài của đường hai chiều được đề xuất thứ j nối giữa hai nút uj và vj.

Dữ liệu ra

Với mỗi bộ dữ liệu, ghi ra trên một dòng độ dài nhỏ nhất có thể của đường đi ngắn nhất giữa hai nút trọng yếu sau khi xây dựng xong một đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ s đến t, ghi -1.

Dữ liệu vào
1
4 5 3 1 4
1 2 13
2 3 19
3 1 25
3 4 17
4 1 18
1 3 23
2 3 5
2 4 25	

Dữ liệu ra
35

hide comments
junior97: 2018-08-21 15:04:41

copy the graph and connect the k roads between them, run dijk just once .

s_a_k_s_h_a_m: 2018-07-08 18:48:10

a good problem
you need to apply dijkstra two times - a single source dijkstra for 's' (d1) and a single sink dijkstra for 't' (d2)
s->t=s->uj-vj->t
now check d1[uj]+d2[vj]+qj,d1[vj]+d2[uj]+qj for minimum

be1035016: 2018-07-01 12:58:26

nice problem

Bác Ba Phì: 2018-06-30 05:57:33

2000 AC submissions, and only 5 of them are in Java. I think the time limit is way too strict for Java.

shahi9935: 2018-06-09 04:11:18

Thanku @ansh_gupta788 and @sherlock11 for your thoughts

sherlock11: 2018-04-13 18:48:37

the problem states that " use at most one road and not exactly one road"........this costed me 3 WA...
this is very nice problem on diJkstra...HAPPY CODING!!!!!!

Last edit: 2018-04-14 11:09:51
ansh_gupta788: 2018-04-12 21:41:08

When i tried it for the first time , it seemed to be a very hard problem . But now when i tried after a month , I did it in the very first attempt :)

racse: 2018-04-01 11:52:20

Best Problem on dijkstra's algorithm that i have solved.

hugo_go2308: 2018-03-17 20:09:10

I have solved this issue on C++, but the same algorithm does not work with Java. I got a runtime error (NZEC). Have an idea that reason in the reader from the console. may I ask you how you read data from console by java? Thank you in advance

chetan4060: 2018-03-13 13:47:38

if wrong ,check for no path condition:)


Added by:Duc
Date:2009-01-04
Time limit:0.140s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Regional, Ho Chi Minh City 2008