Đường đi ngắn nhất với Floyd-Warshall


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Cho đồ thị vô hướng liên thông có $N$ đỉnh và $M$ cạnh. Cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$ có trọng số $w_i$. Hãy tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh sử dụng thuật toán Floyd-Warshall.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $N, M \ (1\le N,M \le 10^2)$;
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i, w_i \ (1\le u_i, v_i \le N; u_i \neq v_i; 1\le w_i \le 10^2)$.

Dữ liệu đảm bảo không có hai cạnh nào chúng kết nối hai đỉnh.

Kết quả

  • In trên $N$ dòng, mỗi dòng in $N$ số nguyên. Với số nguyên thứ $j$ ở dòng thứ $i$ là đường đi ngắn nhất từ đỉnh $i$ đến đỉnh $j$. Các số nguyên trên một dòng cách nhau một dấu cách.

Ví dụ

Ví dụ 1

input

5 6
1 3 3
2 4 2
3 5 5
2 5 1
1 5 4
4 5 1

output

0 5 3 5 4 
5 0 6 2 1 
3 6 0 6 5 
5 2 6 0 1 
4 1 5 1 0

Comments

There are no comments at the moment.