Hai đường đi
View as PDF
Submit solution
Points:
0.21 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Một mạng giao thông gồm ~N~ nút giao thông, và có ~M~ đường hai chiều nối một số cặp nút, thông tin về một đường gồm ba số nguyên dương ~u, v~ là tên hai nút đầu mút của đường, và ~l~ là độ dài đoạn đường đó. Biết rằng hai nút giao thông bất kì có không quá ~1~ đường hai chiều nhận chúng làm hai đầu mút.
Cho hai nút giao thông ~s~ và ~f~, hãy tìm hai đường đi nối giữa ~s~ với ~f~ sao cho hai trên hai đường không có cạnh nào được đi qua hai lần và tổng độ dài ~2~ đường đi là nhỏ nhất.
Input
- Dòng đầu ghi ~N, M~ ~\left(N \leq 100\right)~
- Dòng thứ ~2~ ghi hai số ~s, f~.
- ~M~ dòng tiếp theo, mỗi dòng mô tả một đường gồm ba số nguyên dương ~u, v, l~.
Output
- Dòng đầu ghi ~T~ là tổng độ dài nhỏ nhất tìm được hoặc ~-1~ nếu không tìm được.
- Nếu tìm được, hai dòng sau, mỗi dòng mô tả một đường đi gồm: số đầu là số nút trên đường đi này, tiếp theo là dãy các nút trên đường đi bắt đầu từ ~s~, kết thúc tại ~f~.
Giới hạn
Phạm vi tính toán là số nguyên ~32 - bit~ có dấu
Sample Input
5 8
1 5
1 2 1
1 4 8
2 3 5
2 4 1
3 5 1
4 3 8
4 5 1
1 3 1
Sample Output
5
3 1 3 5
4 1 2 4 5
Comments
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.