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

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

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 Usada_Pekora @ 2022-09-19 20:57:59

@duoaidaoc 这个 pair 就是一个内置的类型,默认按照第一关键字(first) 排序,第一关键字相同按照第二关键字(second)排序,所以我把 dista 都塞到里面就会按照 dist 排序。


by duoaidaoc @ 2022-09-19 21:08:00

@Zyingyzzz 我明白了,我之前的代码没有考虑到入队后dist还有更改的可能。其实应该把dist直接放入优先队列,每次入队时动态更新。 其实我之前自己手写小根堆的时候,维护堆的性质只考虑了入堆元素的影响,没有考虑其他元素的dist也变了...... 总之感谢大佬解惑,Orz


by 孤弦奏愿 @ 2023-02-20 18:02:44

@Usada_Pekora 赞!我就说为什么写的模板有的题能过有的题就wa.


上一页 |