Problem
Bạn được cung cấp một biểu đồ trọng số có hướng. Tìm đường đi ngắn nhất từ đỉnh này đến đỉnh khác.
Đầu vào
Dòng đầu tiên chứa ba số: N, S và F (1≤N≤100, 1≤S, F≤N), trong đó N – số đỉnh của đồ thị, S – đỉnh ban đầu và F – cuối cùng. Trong N dòng tiếp theo, hãy nhập N số mỗi dòng, không quá 100, – ma trận kề của đồ thị, trong đó -1 có nghĩa là không có cạnh giữa các đỉnh và bất kỳ số không âm nào – sự hiện diện của một cạnh của trọng lượng nhất định. Các số 0 được viết trên đường chéo chính của ma trận.
Đầu ra
Yêu cầu hiển thị tuần tự tất cả các đỉnh của một (bất kỳ) đường đi ngắn nhất hoặc một số -1 nếu không có đường đi giữa các đỉnh đã chỉ định.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |