求答疑,为方便看,只放了最核心的dj代码。
while(!q.empty()){
auto [w,u]=q.top();
q.pop();
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数组来判断?