优先队列Dijkstra只过了第五点，悬关xddd

Crushxl @ 2023-08-13 18:15:14

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n,m,s,cnt,head[MAXN];

struct Edge{int next,to,w;}e[MAXN];

void AddEdge(int u,int v,int w){
    e[++cnt].next = head[u];
    e[cnt].to = v;
    e[cnt].w = w;
    head[u] = cnt;
}

struct Node{
    int to,dis;
    bool operator<(const Node a)const{a.dis<dis;}
};

int check[MAXN],dis[MAXN];
void Dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[s] = 0;
    priority_queue<Node> q;
    q.push({s,0});
    while(!q.empty()){
        Node tmp = q.top();
        q.pop();
        int x = tmp.to;
        if(!check[x]){
            for(int i=head[x];i!=0;i=e[i].next){
                int y = e[i].to;
                if(dis[y] > dis[x]+e[i].w){
                    dis[y] = dis[x]+e[i].w;
                    q.push({y,dis[y]});
                }
            }
        }
        check[x] = 1;
    }
}

int main(){
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w; 
        AddEdge(u,v,w);
    }
    Dijkstra();
    for(int i=1;i<=n;i++){
        cout << dis[i] << " ";
    }
    return 0;
}

by fangzichang @ 2023-08-13 18:24:12

盲猜long long。

by SuperChao @ 2023-08-13 18:31:55

@fangzichang 应该不是long long的问题

by fangzichang @ 2023-08-13 18:37:44

有UB。等我看看。

by SuperChao @ 2023-08-13 18:40:26

重载Node运算符<的时候没有返回值

by fangzichang @ 2023-08-13 18:40:53

重载运算符挂了。

by SuperChao @ 2023-08-13 18:43:08

@fangzichang 哈哈哈万能的氧气(⁎⁍̴̛ᴗ⁍̴̛⁎)

by shalu @ 2023-08-13 18:43:19

@Crushxl code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int n,m,s,cnt,head[MAXN];
struct Edge{
    int next,to,w;
}e[MAXN];
void AddEdge(int u,int v,int w){
    e[++cnt].next = head[u];
    e[cnt].to = v;
    e[cnt].w = w;
    head[u] = cnt;
}

struct Node{
    int to,dis;
    bool operator<(const Node a)const{ return a.dis<dis;}
};

int check[MAXN],dis[MAXN];
void Dijkstra(){
    memset(dis,0x3f3f3f3f3f,sizeof(dis));
    dis[s] = 0;
    priority_queue<Node> q;
    q.push(Node{s,0});
    while(!q.empty()){
        Node tmp = q.top();
        q.pop();
        int x = tmp.to;
        if(!check[x]){
            check[x] = 1;
            for(int i=head[x];i!=0;i=e[i].next){
                int y = e[i].to;
                if(dis[y] > dis[x]+e[i].w){
                    dis[y] = dis[x]+e[i].w;
                    if(!check[y]){
                        q.push({y,dis[y]});
                    }
                }
            }
        }
    }
}

int main(){
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w; 
        AddEdge(u,v,w);
    }
    Dijkstra();
    for(int i=1;i<=n;i++){
        cout << dis[i] << " ";
    }
    return 0;
}

by shalu @ 2023-08-13 18:44:09

@Crushxl 您的重载运算符写挂了，没有returnQAQ

by shalu @ 2023-08-13 18:45:35

@Crushxl

if(dis[y] > dis[x]+e[i].w){
                    dis[y] = dis[x]+e[i].w;
                    if(!check[y]){
                        q.push({y,dis[y]});
                    }

这里，您要if一下，！这个点的check才可以push

by Crushxl @ 2023-08-13 18:51:55

@shalu 谢谢dalao！！！今天初学的链式前向星和和优先队列，重载是一点也不会()