Traffic Network
View as PDF
Submit solution
Points:
0.20 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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.
Input
- 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 \leq 10 000)~, ~m~ ~(m \leq 100 000)~, ~k~ ~(k < 300)~, ~s~ ~(1 \leq s \leq n)~, ~t~ ~(1 \leq t \leq 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 ~d_i~, ~c_i~, ~l_i~ cách nhau bởi dấu trống, trong đó ~l_i~ là độ dài (0 ~< l_i \leq 1000)~ của đường một chiều thứ ~i~ từ nút ~d_i~ đến nút ~c_i~. Dòng thứ ~j~ trong ~k~ dòng tiếp theo chứa ba số nguyên dương ~u_j~, ~v_j~ và ~q_j~ ~(q_j \leq 1000)~ cách nhau bởi dấu trống, trong đó ~q_j~ là độ dài của đường hai chiều được đề xuất thứ ~j~ nối giữa hai nút ~u_j~ và ~v_j~.
Output
- 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~.
Sample Input
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
Sample Output
35
Comments
test 2 la gi v mng oi
có lẽ bạn quên lấy min của d[t] nữa
E bị sai case 2 :(debug chiều tới giờ nản quá r
bạn lấy min của d[t] chưa
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
Theo mình đề bài này chưa rõ lỡ như giữa k cặp đỉnh xây dựng lỡ có 1 cặp đã có đường 1 chiều từ trước thì nếu theo sol bài này là sai.Giả sử u tới v có đường từ v tới u thì sau khi xây dựng đường u v thì độ dài ngắn nhất từ s->u có thể sẽ đi qua v lúc đó đường đi ngắn nhất là độ dài cũ thì kết quả sẽ sai.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.