蒟蒻求助，我这哪里错掉啦，改一整天了破防了，(内含我自己的思路和注释)

duoaidaoc @ 2022-09-19 20:37:09

#include<bits/stdc++.h>
using namespace std;
const int N = 100000;

//链式前向星
struct zzz {
    int to;//指向的节点
    int val;//边权
    int nex;
}e[N];
int top, head[N];

void add(int x,int y,int z) {
    e[++top].to = y;
    e[top].val = z;
    e[top].nex = head[x];
    head[x] = top;
}
//ed of 链式前向星

//vis 数组和 dist 数组
int vis[N];
int dist[N];

//自定义的优先队列，里面存的是dist数组的下标
//小根堆，指dist[i]最小
struct cmp {
    bool operator()(int x, int y) {
        return dist[x] < dist[y];
    }
};
priority_queue<int, vector<int>, cmp> qe;

int main() {
    //读入n m s。
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);

   //依然读数据，因为无向图，所以加两次边
    for (int i = 1;i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }

   //dist 元素设为无穷大
    memset(dist, 127, sizeof(dist));
   //s节点置为初始节点入队且dist置为0
    dist[s] = 0;
    qe.push(s);

   //队列为空的时候说明都访问完毕
    while (!qe.empty()) {
    //将队首出队，访问相邻节点
        int a = qe.top();
        vis[a] = 1;
        qe.pop();

        for (int i = head[a];i;i = e[i].nex) {
        //若没有访问过
            if (vis[e[i].to] == 0) {
            //更新dist
                dist[e[i].to] = min(dist[e[i].to], dist[a] + e[i].val);
            //入队
                qe.push(e[i].to);
            }
        }
    }
   //逐个打印
    for (int i = 1;i <= n;i++) {
        printf("%d ", dist[i]);
    }
    return 0;
}

by duoaidaoc @ 2022-09-19 20:38:51

球球拉，18昏，只过了4

by TimSwn090306 @ 2022-09-19 20:42:07

@duoaidaoc 你的dist初始值是不是有点小啦（怀疑

by duoaidaoc @ 2022-09-19 20:44:52

还有N开到1000000也没用。

by duoaidaoc @ 2022-09-19 20:46:20

@TimSwn090306 百度上说设置127就是无穷大啊

by Usada_Pekora @ 2022-09-19 20:47:07

@duoaidaoc “无向图”

by Usada_Pekora @ 2022-09-19 20:47:56

cmp 里改成大于，priority_queue 是大根堆。

by duoaidaoc @ 2022-09-19 20:48:38

@Zyingyzzz 感谢！我真是眼瞎了，再去试试

by Usada_Pekora @ 2022-09-19 20:51:49

@duoaidaoc 改好了。

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;

//链式前向星
struct zzz {
    int to;//指向的节点
    int val;//边权
    int nex;
}e[N];
int top, head[N];

void add(int x,int y,int z) {
    e[++top].to = y;
    e[top].val = z;
    e[top].nex = head[x];
    head[x] = top;
}
//ed of 链式前向星

//vis 数组和 dist 数组
int vis[N];
int dist[N];

//自定义的优先队列，里面存的是dist数组的下标
//小根堆，指dist[i]最小
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > qe;

int main() {
    //读入n m s。
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);

   //依然读数据，因为无向图，所以加两次边
    for (int i = 1;i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
//        add(y, x, z);
    }

   //dist 元素设为无穷大
    memset(dist, 127, sizeof(dist));
   //s节点置为初始节点入队且dist置为0
    dist[s] = 0;
    qe.push(make_pair(0, s));

   //队列为空的时候说明都访问完毕
    while (!qe.empty()) {
    //将队首出队，访问相邻节点
        int a = qe.top().second;

        qe.pop();
        if (vis[a]) continue;
        vis[a] = 1;
        for (int i = head[a];i;i = e[i].nex) {
        //若没有访问过
            if (vis[e[i].to] == 0) {
            //更新dist
                dist[e[i].to] = min(dist[e[i].to], dist[a] + e[i].val);
            //入队
                qe.push(make_pair(dist[e[i].to], e[i].to));
            }
        }
    }
   //逐个打印
    for (int i = 1;i <= n;i++) {
        printf("%d ", dist[i]);
    }
    return 0;
}

by Usada_Pekora @ 2022-09-19 20:52:53

不要用一直在更新的 dist 去比较，一旦 dist 更新了以后堆序会出问题。

by duoaidaoc @ 2022-09-19 20:55:38

@Zyingyzzz 原来如此！感谢！ 我本来是c语言转过来写题的，c++优先队列只是抄了样子，还不知道什么是pair