优先队列WA 求调

P4779 【模板】单源最短路径（标准版）

hupan8845074 @ 2024-10-19 00:54:41

刚学dijkstra，不知道有什么问题。。


#include<bits/stdc++.h>
const int N=2e6;
const int inf=INT_MAX;
using namespace std;
struct jntm{
    int to,w;
};
struct que{
    int u,w;
    bool operator <(const que &x) const{
        return x.w < w ;
    }
};
int n,m,s;
int d[N],vis[N];
vector <jntm> edge[N];
priority_queue<que> q ;
void dj(int ss){
    for(int i=0;i<=n;i++){
        d[i]=inf;
    } 
    d[ss]=0;
    q.push((que){ss,0});
    for(int i=1;i<=n;i++){
        int u=q.top().u;
        while(!q.empty()) q.pop();

        for(auto ed:edge[u]){
            int to=ed.to , w=ed.w;
            if(d[to]>d[u]+w){
                d[to]=d[u]+w;
                q.push((que){to,d[to]});
            }
        }
    }
}
int main(){
    int a,b,x;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>x;
        edge[a].push_back({b,x});
    }
    dj(s);
    for(int i=1;i<=n;i++){
        cout<<d[i]<<" ";
    }
    return 0;
}

by hupan8845074 @ 2024-10-19 00:55:19

只能过样例

by masonxiong @ 2024-10-19 02:57:33

@hupan8845074

什么神经写法。您每次取完队首之后直接把整个队列清空了？

by postpone @ 2024-10-19 03:28:39

        while (!q.empty()) {
            auto [D, x] = q.top();
            q.pop();

            if (D > dis[x])
                continue;

            for (auto &&[y, w] : adj[x]) {
                if (dis[y] > dis[x] + w) {
                    dis[y] = dis[x] + w;
                    q.push({dis[y], y});
                }
            }
        }

by Huangjh1 @ 2024-10-20 19:06:23

// 错误：while(!q.empty()) q.pop() // 原因：每次找到一条路以后就把队列清空而没有保存堆顶和第二大的信息 // 解决： while(!q.empty) { int u = q.top().seond; q.pop(); ... }

by Huangjh1 @ 2024-10-20 19:07:52

@Huangjh1 修正格式：

|