4410: 【例18-2】图的存储-邻接表
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
现希望将第二张图和第三张图 存进计算机。 可以使用邻接矩阵存储一张图： 记 v[i][j] 表示从 i 到 j 的边权。 如果不通可以设置为 0 或者 inf （一个很大的数字）。 无向图的邻接矩阵是对称的， 有向图的邻接矩阵则不对称。把邻接表转换为邻接矩阵。
样例输入 复制
4 6
1 3 2
2 1 1
2 4 6
3 4 5
4 1 4
4 1 3样例输出 复制
0 0 2 0
1 0 0 6
0 0 0 5
3 0 0 0提示
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
struct edge {
// 记录边的终点，边权的结构体
int to, cost;
};
int n, m; // 图有 n 个点 m 条边
vector <edge> p[MAXN]; // 邻接表
int v[MAXN][MAXN]; // 邻接矩阵
int main(){
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, l;
cin >> u >> v >> l;
p[ u ].push_back((edge) {v, l});
// p[ v ].push_back((edge){u, l});
// 无向图邻接表要加一条反方向的边
}
// 遍历邻接表，把邻接表转换为邻接矩阵
for (int i = 1; i <= n; i++)
for (int j = 0; j < p[i].size(); j++)
v[i][p[i][j].to] = p[i][j].cost;
// 输出邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cout<<v[i][j]<<' ';
cout<<'\n';
}
return 0;
}