Cho đồ thị có hướng đỉnh đánh số từ đến , cung và hai đỉnh , .
Hãy tìm một đường đi ngắn nhất (đi qua ít cạnh nhất) từ đỉnh tới đỉnh .
Dữ liệu:
- Dòng đầu chứa bốn số nguyên dương ;
- dòng sau, mỗi dòng chứa một cặp số nguyên cho biết có một cung nối từ đến của đồ thị .
Kết quả:
- Nếu không có đường đi đơn từ đến , ghi ra , ngược lại, ghi kết quả theo định dạng:
- Dòng đầu ghi số nguyên dương là độ dài đường đi ngắn nhất (số cạnh đi qua);
- Dòng sau ghi dãy đỉnh trên đường đi (xuất phát từ , kết thúc tại ), nếu có nhiều đường đi (ngắn nhất) thì ghi ra đường đi ngắn nhất bất kỳ.
Ví dụ:
Dữ liệu:
7 7 1 2
1 2
1 3
1 5
2 4
2 6
3 7
5 6
Kết quả:
