Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho đồ thị có hướng có trọng số gồm n đỉnh và m cung.
Tìm độ dài đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.
Lưu ý: trọng số có thể âm.
INPUT
Dòng đầu là 2 số nguyên dương: n, m (n ≤ 420; m ≤ $10^6$)
m dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c cho biết có cung u-v với trọng số c. (1 ≤ u, v ≤ n; |c| ≤ $10^6$).
OUTPUT
Ghi ra n dòng, mỗi dòng gồm n số: số thứ j trên dòng i là độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j. Nếu không có đường đi thì ghi ra chữ X.
VÍ DỤ
Input
5 7
1 3 8
1 5 -7
4 1 12
2 5 8
2 4 5
3 5 1
5 4 -4
Output
0 X 8 -11 -7
16 0 24 4 8
9 X 0 -3 1
12 X 20 0 5
8 X 16 -4 0
Bình luận