Cho đơn đồ thị có hướng (không có khuyên) trọng số dương có đỉnh. Đồ thị được cho bởi ma trận kề , trong đó:
- là trọng số của cung đi từ đỉnh đến đỉnh
- nếu không có cung đi từ đỉnh đến đỉnh .
Yêu cầu: Hãy tìm đường đi ngắn nhất qua đúng cạnh của đồ thị. Tức là tìm ma trận , trong đó:
- nếu không có đường đi từ đến qua đúng cạnh của đồ thị
- là độ dài đường đi ngắn nhất từ đến qua đúng cạnh của đồ thị.
Dữ liệu vào:
- Dòng đầu chứa hai số nguyên dương ;
- dòng sau, dòng thứ chứa số nguyên không âm .
Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra:
- Gồm dòng, dòng thứ chứa số nguyên không âm . Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Ví dụ:
Dữ liệu vào:
4 2
0 1 0 0
0 0 1 3
3 0 0 1
1 0 0 0
Dữ liệu ra:
0 0 2 4
4 0 0 2
2 4 0 0
0 2 0 0
Giới hạn:
- .
