这里有两份 Dijkstra 算法的代码：

第一份：

void dijkstra(int x){
    memset(vis, false, sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=0x7fffffff;
    dis[x] = 0;
    q.push(make_pair(0, x));
    while(!q.empty()){
        pair<int, int> now=q.top();
        q.pop();
        if(vis[now.second])
            continue;
        vis[now.second] = 1;
        for (int i = head[now.second]; i;i=a[i].nxt){
            if(a[i].w + now.first<dis[a[i].to]){
                dis[a[i].to] = a[i].w + now.first;
                if(!vis[a[i].to]) q.push(make_pair(dis[a[i].to], a[i].to));
            }
        }
    }
}

第二份：

void dijkstra(int x){
    memset(vis, false, sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=0x7fffffff;
    dis[x] = 0;
    q.push(make_pair(0, x));
    while(!q.empty()){
        pair<int, int> now=q.top();
        q.pop();
        if(vis[now.second])
            continue;
        vis[now.second] = 1;
        for (int i = head[now.second]; i;i=a[i].nxt){
            if(a[i].w + now.first<dis[a[i].to]&&!vis[a[i].to]){
                dis[a[i].to] = a[i].w + now.first;
                q.push(make_pair(dis[a[i].to], a[i].to));
            }
        }
    }
}

两份代码的唯一区别在于遍历当前点所连的边的判断过程中，判断条件 !vis[a[i].to] 的位置。两份代码均能通过最短路板子题。

蒟蒻想问一下，这两份代码那一份是正确的，亦或是两份均正确？