ĐƯỜNG ĐI GIỮA MỌI CẶP ĐỈNH

Xem dạng PDF

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:
hsgtin.vn/sach
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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.