萌新刚学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 lzyqwq @ 2022-09-03 09:24:10

这样显然是错误的。

小根堆里排序的关键字应当是节点到源点的距离，而不是节点编号

by Greenzhe @ 2022-09-03 09:25:13

@蒟蒻·廖子阳 大佬但我用的是cmp排的啊

by lzyqwq @ 2022-09-03 09:30:10

@蒟蒻·廖子阳 你垃圾

by lzyqwq @ 2022-09-03 09:30:55

@Greenzhe 那你看看你的重载

为什么是 bool operator()

我没这样写过，不知道对不对

by too_simple @ 2022-09-03 09:32:37

@Greenzhe 为啥不定义一个结构体呢？

by FiraCode @ 2022-09-03 09:33:22

#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();
        // cout << x << endl;
        q.pop();
        vis[x] = false;
        for(int i=0;i<rel[x].size();++i){
            int y=rel[x][i].v;
            // cout << '\t' << y << ' ' << dis[x] << endl;
            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);
                }
            }
        }
    }
}

改了一下，对了，就是在q.pop()之后加了vis[x]=false就过了

by lzyqwq @ 2022-09-03 09:33:32

@李佳和 同问

by lzyqwq @ 2022-09-03 09:34:04

@FiraCode 怎么感觉这样就有 spfa 那味了

by FiraCode @ 2022-09-03 09:34:32

@Greenzhe

by FiraCode @ 2022-09-03 09:35:01

@蒟蒻·廖子阳 确实