Submit solution
Points:
0.60 (partial)
Time limit:
0.38s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem type
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 , S , F~ ~\left(N \leq 50000;\text{ } M \leq 100000\right)~
- ~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~ ~\left(u,v \leq N;\text{ } l \leq 2 \times 10^9\right)~
Output
Gồm ~1~ dòng duy nhất là tổng độ dài nhỏ nhất tìm được hoặc ghi ra ~-1~ nếu không có đường đi
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
Comments