怎样建立带权有向图的邻接表

建立带权有向图的邻接表需要使用一个数组来存储每个顶点的出边，数组的每个元素都是一个链表，链表中存储了从该顶点出发的所有边。链表中的每个节点都包含一个指向目标顶点的指针和该边的权重。

下面是一个示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 定义边的结构体
struct Edge {
    int to;       // 目标顶点
    int weight;   // 边的权重
    Edge* next;   // 指向下一条边的指针
};

// 定义顶点的结构体
struct Vertex {
    int val;     // 顶点的值
    Edge* head;  // 指向第一条边的指针
};

int main() {
    int n, m;
    cin >> n >> m;  // n为顶点数，m为边数

    // 初始化邻接表
    vector<Vertex> adj_list(n);

    // 读入每条边的信息，建立邻接表
    for (int i = 0; i < m; i++) {
        int from, to, weight;
        cin >> from >> to >> weight;

        // 添加一条从from到to的边
        Edge* e = new Edge{to, weight, nullptr};
        if (adj_list[from].head == nullptr) {
            adj_list[from].head = e;
        } else {
            e->next = adj_list[from].head;
            adj_list[from].head = e;
        }
    }

    // 打印邻接表
    for (int i = 0; i < n; i++) {
        cout << i << ": ";
        Edge* p = adj_list[i].head;
        while (p != nullptr) {
            cout << "(" << p->to << "," << p->weight << ") ";
            p = p->next;
        }
        cout << endl;
    }

    return 0;
}

在这个示例中，我们使用了一个vector来存储所有的顶点，每个顶点都对应一个邻接表。对于每条边，我们只需要添加一条从起点到终点的边即可。如果起点的邻接表中已经存在其他的边，我们只需要将新的边插入到链表的头部即可。