关于dj算法的细节提问
查看原帖
关于dj算法的细节提问
972179
222021321081024_楼主2024/2/28 13:13

求答疑,为方便看,只放了最核心的dj代码。

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

//        if(dist[u]<w) continue;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=graph[i].next){
            int to=graph[i].to;
            if(dist[to]>dist[u]+graph[i].w){
                dist[to]=dist[u]+graph[i].w;
                q.emplace(-dist[to],to);
                count[to]=count[u];
            }
            else if(dist[to]==dist[u]+graph[i].w) count[to]+=count[u];
        }
    }

在一般的dj跑最短路,直接用if(dist[u]<w)判是否需要更新貌似就行,为什么这里不可以这样子呢?需要单独开一个vis数组来判断?

2024/2/28 13:13
加载中...