链式前向星

原理

见《进阶指南》第62页。

代码

const int N = 100010, M = 500010;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}

memest(head, -1, sizeof(head));

for (int i = head[cur]; i != -1; i = e[i].next) {
    int to = e[i].to, w = e[i].w;
    // ...
}