1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <algorithm>
using namespace std;
int	n, m, i, a1, a2, a3, a[102][102];
int main() {
	cin >> n >> m;
	fill(a[0], a[0] + 10404, 987654321);
	for (i = 0; i < m; i++) {
		cin >> a1 >> a2 >> a3;
		a[a1][a2] = min(a[a1][a2], a3);
	}
	for (i = 1; i <= n; i++) 
		for (int t = 1; t <= n; t++)
			for (int y = 1; y <= n; y++)
				if (t == y) a[t][y] = 0;
				else	a[t][y] = min(a[t][y], a[t][i] + a[i][y]);
	for (i = 1; i <= n; i++) {
		for (int t = 1; t <= n; t++)
			if (a[i][t] == 987654321)	cout << "0 ";
			else	cout << a[i][t] << " ";
		cout << endl;
	}
}