用邻接表存储带权图和之前的实现方式略有区别，我们需要用一个结构体来记录一条边连接的点和这条边的边权，然后用一个vector来存储若干个结构体，实际上就是把一个点所连接的点以及这条边的边权"打包"起来放到邻接表中。
结构体的定义举例如下：
struct node { int v; // 用来记录连接的点 int w; // 用来记录这条边的边权 };我们通常把有向图中加入一条边写成一个函数，例如加入一条有向边 (u,v) 、边权为 w ，就可以用如下的函数来实现（我们需要把图定义成全局变量）。
vector<node> G[105]; // 插入有向边 void insert(int u, int v, int w) { node temp; temp.v = v; temp.w = w; G[u].push_back(temp); }而插入一条无向边，实际上相当于插入两条方向相反的有向边：
// 插入无向边 void insert2(int u, int v, int w) { insert(u, v, w); insert(v, u, w); } 带权图邻接表的实现 #include <iostream> #include <vector> using namespace std; const int maxn = 105; struct node { int v; int w; }; vector<node> G[maxn]; void insert(int u, int v, int w) { node temp; temp.v = v; temp.w = w; G[u].push_back(temp); } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; insert(u, v, w); } for (int i = 1; i <= n; i++) { for (int j = 0; j < G[i].size(); j++) { cout << i << " " << G[i][j].v << " " << G[i][j].w << endl; } } return 0; }终于写完了……累死我了……
欢迎大家指出错误或给出建议
欢迎大家指出错误或给出建议
欢迎大家指出错误或给出建议
重要的事说三遍……
最后不要脸的求赞+关注+收藏