Dijkstra算法及邻接表 C++

Question

priority_queue<pair<int,int>>q;//大根堆-小根堆
    memset(d,0x3f,sizeof(d);
    memset(v,0,sizeof(v));
    d[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    int x=q.top().second;q.pop();
    if(v[x])continue;
    v[x]=1;
    for(int i=head[x];i;i=Next[i])
    int y=ver[i],z=edge[i];
    if(d[y]>d[x]+z){
        d[y]=d[x]+z;
        q.push(make_pair(-d[y],y));
    }
    } 

如上，请问一下：

while(q.size())
if(v[x])continue;
for(int i=head[x];i;i=Next[i])

各是什么意思？还有邻接表的原理是什么？麻烦了！

Answer 1

邻接表你可以理解为多个链表，每个链表的头是一个节点，而你添加一条边add（a,b,c）相当于给a增添一个出度b长度为c，而 next[a]中储存的是就是a所有的出度的地址，next存储的是下一个出度的地址，ver[i]就是出度点的标号，edge[i]头节点到出度的距离，dj的基本思路是每次选取一个离原点最近的边来更新其他点的距离，我们先将{0，1}加入堆中，堆排序pair根据first优先原则，所以意思就是堆中1号点到一号点的距离为0，那么此时会用1号点先更新它出度，并且每个点有且只会被加入一次，我们将它打上标记，如果堆中已经加入过这个最短边，我们直接将它continue，否则而循环的终点就是没有边再被更新的时候，也就是没有东西可以入队了，循环结束。