为什么链式向前星存图的时间和空间都比邻接表存图小

P4779 【模板】单源最短路径(标准版)

Light_LE @ 2024-10-04 10:06:50

rt

// 链式向前星存图
#include <bits/stdc++.h>
#define maxn 100003
using namespace std;
struct Edge {
    int v, w, next;
}edge[200003];
struct Data {
    int dis, pos;
    bool operator < (const Data &x) const {
        return x.dis < dis;
    }
};
int n, m, s, cnt, vis[maxn], dis[maxn], head[maxn];
priority_queue<Data> q;
void add(int u, int v, int w) {
    cnt++;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push((Data){0, s});

    while (q.size()) {
        Data f = q.top();
        q.pop();
        int pos = f.pos;

        if (vis[pos]) {
            continue;
        }
        vis[pos] = 1;

        for (int i = head[pos]; i; i = edge[i].next) {
            int v = edge[i].v, w = edge[i].w;
            if (dis[v] > dis[pos] + w) {
                dis[v] = dis[pos] + w;
                if (vis[v] == 0) {
                    q.push((Data){dis[v], v});
                }
            }
        }
    }
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }

    dijkstra();

    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}
// 邻接表存图
#include <bits/stdc++.h>
#define maxn 100003
using namespace std;
struct GraphData {
    int v, w;
};
struct Data {
    int dis, u;
    bool operator < (const Data &x) const {
        return x.dis < dis;
    }
};
int n, m, s, vis[maxn], dis[maxn];
vector<GraphData> G[200003];
priority_queue<Data> q;
void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push((Data){0, s});

    while (q.size()) {
        Data f = q.top();
        q.pop();
        int u = f.u;

        if (vis[u]) {
            continue;
        }
        vis[u] = 1;

        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v, w = G[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (vis[v] == 0) {
                    q.push((Data){dis[v], v});
                }
            }
        }
    }
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back((GraphData){v, w});
    }

    dijkstra();

    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}

by Rigel @ 2024-10-04 10:08:50

你觉得呢。


by realheizi @ 2024-10-04 10:09:13

同问


by Hhy882577 @ 2024-10-06 22:29:51

@Light_LE 链式前向星不是邻接表的一种吗? 其次,邻接表第二种形式是 vector,至于它,在没有边权时不用 pair,效率和前向星差不多,但由于 vector 自身机制是自动扩充两倍空间保证效率和不炸储存,因此总体效率是要比前向星低的(链式前向星本质为链表),再加上大部分题都有边权要开 pair,雪上加霜


by Hhy882577 @ 2024-10-06 22:31:00

这也解释了为什么 vector 在大概 1e6 的时候要炸空间


by Hhy882577 @ 2024-10-06 22:32:38

但据说动态开点不能用链式前向星(说错了的地方勿喷蒟蒻)


|