萌新刚学Dij板子求调，WA52pts只对点2,5,6

Greenzhe @ 2022-09-03 09:10:54

#include <bits/stdc++.h>
using namespace std;

int n,m,s;
int dis[100005];
bool vis[100005];
struct edge{
    int v,w; //v终点，w权值
};
vector<edge> rel[100005]; 
const int INF=0x3f3f3f3f;

void dijkstra();

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        rel[u].push_back({v,w});
    }
    memset(dis,0x3f,sizeof(dis));
    dijkstra();
    for(int i=1;i<=n;++i)
        printf("%d ",dis[i]);
    printf("\n");
    return 0;
}
struct cmp{
    bool operator()(int a,int b){
        return dis[a]>dis[b];
    }
}; //自定义比较仿函数，用于小根堆
void dijkstra(){
    priority_queue<int,vector<int>,cmp> q;
    dis[s]=0;
    vis[s]=true;
    q.push(s);
    while(!q.empty()){
        int x=q.top();
        q.pop();
        for(int i=0;i<rel[x].size();++i){
            int y=rel[x][i].v;
            if(dis[x]+rel[x][i].w<dis[y]){
                dis[y]=dis[x]+rel[x][i].w;
                if(!vis[y]){
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
    }
}

by Zvelig1205 @ 2022-09-03 10:01:06

@yinhee 这种只能叫堆优 spfa 吧，dij 不是这样写的。

by Zvelig1205 @ 2022-09-03 10:04:44

总感觉哪里怪怪的

by cxqghzj @ 2022-09-03 11:10:40

这就是堆优spfa吧

by Greenzhe @ 2022-09-09 15:42:10

upd: 2022/9/9

这里补充一下，这个程序的错误在于这里：

struct cmp{
    bool operator()(int a,int b){
        return dis[a]>dis[b];
    }
}; //自定义比较仿函数，用于小根堆

这种写法破坏了堆的结构，a进优先队列时比b小，可能出队时就比b大了。一定要注意，堆中元素的大小关系必须保持不变。

（来自 Pecco 大佬的专栏 https://zhuanlan.zhihu.com/p/96621396）

至于为什么加了一句 vis[x]=false 就会 AC，因为加了这句以后某种程度上已经变成 spfa 了（

所以建议大家还是好好写结构体

by Greenzhe @ 2022-09-09 16:41:56

还有一处错误，这里

if(!vis[y]){
    vis[y]=true;
    q.push(y);
}

写成类似 SPFA 了。

正确写法：

struct node{
    int id,dis;
};
struct cmp{
    bool operator()(node &a,node &b){
        return a.dis>b.dis;
    }
};
void dijkstra(){
    priority_queue<node,vector<node>,cmp> q;
    dis[s]=0;
    q.push({s,dis[s]});
    while(!q.empty()){
        int x=q.top().id;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int i=0;i<rel[x].size();++i){
            int y=rel[x][i].v;
            if(dis[x]+rel[x][i].w<dis[y]){
                dis[y]=dis[x]+rel[x][i].w;
                if(!vis[y]){
                    q.push({y,dis[y]});
                }
            }
        }
    }
}

发一下，以免误人子弟。

希望对路过的你有帮助。