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 (N ≤ 100)
- 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.
Mọi người chỉ cần đưa ra hướng giải quyết.
Cái đường đi ngắn nhất thứ nhất chắc chắn dung disjtra rồi. Còn cái thứ 2 thì mình không biết làm sao? mong mọi người chỉ dẫn.
Thank mọi người nhiều
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?