链式前向星存储出错求调!!!

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

xiaobu_dean @ 2023-11-01 12:59:48

// 堆优化的dijkstra算法
// 通过使用优先对列优化了朴素dijkstra算法中找离当前源点最近的点
// q.push_back({w,v}),w为v到源点的距离
// 将权值放在第一位是因为pair中会优先对第一个元素排序

// 1.邻接表存储
/*#include <bits/stdc++.h>
#define inf INT_MAX;
using namespace std;

using ll = long long ;
const int N = 1e5 + 50;
int n,m,s;
struct edge {int v,w;};
vector<edge> e[N];
int d[N];
bool vis[N];
priority_queue<pair<int,int> > q;

void dijkstra(int s) {
    for (int i = 1;i <= n; i++) d[i] = inf;
    d[s] = 0;
    q.push({0,s});
    while (q.size()) {
        auto t = q.top(); q.pop();
        int u = t.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (auto c:e[u]) {
            int v = c.v; int w = c.w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w; // 松弛操作
                q.push({-d[v],v});
            }
        }
    }
} 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1;i <= m; i++) {
        int u,v,w; cin >> u >> v >> w;
        e[u].push_back({v,w});
    }
    dijkstra(s);
    for (int i = 1;i <= n; i++) cout << d[i] << " ";
    return 0;
}*/

// 2.链式前向星存储
#include <bits/stdc++.h>
#define inf INT_MAX;
using namespace std;

using ll = long long ;
const int N = 1e5 + 50 ;
int n,m,s;
struct edge {
    int to,ne,w;
}edge[N];
int head[N],cnt;
void add(int u,int v,int w) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].ne = head[u];
    head[u] = cnt;
}
int d[N];
bool vis[N];
priority_queue<pair<int,int> > q;
void dijkstra(int s) {
    for (int i = 1;i <= n; i++) d[i] = inf;
    d[s] = 0;
    q.push({0,s});
    while (q.size()) {
        auto t = q.top();q.pop();
        int u = t.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u];i>0;i = edge[i].ne) {
            int v = edge[i].to;
            int w = edge[i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({-d[v],v}); // 权值是-d[v],不是w也不是d[v]
            }
        } 
    } 
}
// 以上为链式前向星模版
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1;i <= m; i++) {
        int u,v,w; cin >> u >> v >> w;
        add(u,v,w);
    }
    dijkstra(s);
    for (int i = 1;i <= n; i++) cout << d[i] << " ";
    return 0;
}

上面注释掉的是我用vector模拟邻接表存储的,已经AC了,然后想着用链式前向星写一下,结果RE了四个点


by Aesyl @ 2023-11-01 13:12:45

邻接表大小为点数,前向星大小为边数(双向算两条边)


by Aesyl @ 2023-11-01 13:13:25

本题边数为2x10^5


by xiaobu_dean @ 2023-11-01 18:01:25

@Daffod_Tequila orz


|