图的存储(Storing a Graph)

题目描述

存储一张图和存储一棵树的方法完全一样，仍然可以使用邻接矩阵：用一个二维数组 a 记录节点之间的边。

不同的是，图中的边可能带有边权（比如两个城市之间的距离）。这时邻接矩阵中：

• 如果节点 u 和节点 v 之间有一条权值为 w 的边，就令 a[u][v] = w；
• 如果没有边，就令 a[u][v] = 0。

图是无向的，所以每条边 u-v（权值 w）要在矩阵中记录两个位置：a[u][v] = w 且 a[v][u] = w，矩阵仍然关于主对角线对称。

现在有一张 n 个顶点、m 条边的无向带权图，已知每条边连接的两个顶点编号和边权。请你把这张图存入邻接矩阵，并把矩阵打印出来。

输入格式

第一行两个整数 n 和 m，分别表示顶点个数和边的条数。

接下来 m 行，每行三个整数 u、v、w，表示顶点 u 和顶点 v 之间有一条权值为 w 的边。

输出格式

输出一个 n 行 n 列的邻接矩阵：

• 每一行的 n 个数字之间用一个空格隔开；
• 有边的位置输出该边的边权，没有边的位置输出 0；
• 矩阵关于主对角线对称。

样例输入

5 7
1 2 12
1 3 10
2 3 18
2 4 10
2 5 15
3 5 9
4 5 7

样例输出

0 12 10 0 0
12 0 18 10 15
10 18 0 0 9
0 10 0 0 7
0 15 9 7 0

数据范围

• 1 ≤ n ≤ 1000
• 0 ≤ m ≤ n(n-1)/2
• 1 ≤ u, v ≤ n，u ≠ v
• 1 ≤ w ≤ 10000
• 保证图中没有重边和自环

提示

读入每条边 u v w 后，同时做两个赋值：a[u][v] = w; a[v][u] = w;，最后按行打印矩阵即可。边权可能是多位数，直接用整数输出即可。