今天早上起来写一下迪杰斯特拉算法的优先队列优化代码，发现一些错误。

问题

1. 检查st状态应该是访问当前ver顶点时进行判断，如果当前ver没有访问过，那么将之置为已访问，并且以该顶点为起点遍历其可达的其他点，更新它们的距离。如果其距离能够被更新，那么将其加入优先队列。
2. 初始化放在dijkstra较好，而不是额外写一个函数，这样很容易忘记调用。

chatgpt点评

在你的代码和正确代码之间，存在几个关键的区别和错误。下面我将逐一指出并总结你的错误：

1. 不必要的初始化

在你的代码中，使用了 memset(st, 0, sizeof st); 在 dijkstra 函数中重复初始化 st 数组，而正确代码只在需要时检查 st 数组的状态。这种重复的初始化不仅多余，还可能引起效率问题。

2. 数组大小和边界条件

你在代码中设置的数组大小 const int N = 2e6 + 10; 可能是基于问题规模过于慷慨的估计。正确的代码中使用 const int N = 1e6 + 10; 可能更贴合实际问题的规模。

3. 错误的数组访问和更新

在你的 dijkstra 函数中，你没有检查顶点是否已经被处理 (st[ver] == 1)。你的代码在每次取出队列顶的元素后立即标记为已访问，而正确的做法应该是检查这个顶点是否已经被处理过。如果未处理，再进行更新并标记。这会导致重复处理某些顶点，增加不必要的计算。

4. 优先队列的使用

你的代码和正确代码都使用了优先队列来优化 Dijkstra 算法，但你的代码在更新 dist 数组后直接将新距离推入队列中，而没有检查顶点是否已经被访问过。正确的做法是只有当找到更短的路径时，才将其加入优先队列，并在取出顶点时检查是否访问过。

5. 代码结构和清晰度

你的代码在 init 函数中对 dist 数组使用了 memset(dist, 0x3f, sizeof dist); 进行初始化，这是正确的。但在主函数中又进行了一次全局变量的初始化，这种重复是不必要的。正确代码中将所有初始化放在 main 函数开头，避免了混乱和重复。

总结

• 数组初始化和访问：确保你的初始化逻辑符合预期，避免重复初始化。
• 算法逻辑：在实现算法时，确保遵循算法的逻辑正确性，如 Dijkstra 算法中对已处理节点的检查。
• 代码组织：保持代码的清晰和组织性，避免不必要的代码重复和过度复杂的实现。

调整这些错误后，你的代码应该能更加高效且易于理解。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
const int N=2e6+10;
int h[N],ne[N],w[N],e[N],idx;
int st[N];
int dist[N];
priority_queue<PII,vector<PII>,greater<PII>>q;
void init(){
    idx=0;
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
}
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void dijkstra(){
    dist[1]=0;
    q.push({0,1});
    while(!q.empty()){
        PII t=q.top();
        q.pop();
        int ver=t.second;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(st[j])continue;
            if(dist[j]>dist[ver]+w[i]){
            dist[j]=dist[ver]+w[i];
            q.push({dist[j],j});

            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    init();
    int n,m;cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra();
    cout<<(dist[n]==0x3f3f3f3f?-1:dist[n])<<endl;
}