G=(V,E)是赋权有向图，其中一个顶点为s。每条边的权值均

//迪杰特斯拉的堆优化算法。

//将最原本的迪杰特斯拉算法的第二重循环使用堆，就能达到要求

void down(int x)
{
    x<<=1;
    if (x>t) return;
    if (x<t&&d[s[x+1]]<d[s[x]]) x++;
    if (d[s[x]]>=d[s[x>>1]]) return;
    swap(s[x],s[x>>1]);
    swap(p[s[x]],p[s[x>>1]]);
    down(x);
}
void up(int x)
{
    if (x==1||d[s[x>>1]]<=d[s[x]]) return;
    swap(s[x],s[x>>1]);
    swap(p[s[x]],p[s[x>>1]]);
    up(x>>1);
}
void dijkstra()
{
    int i,x,k;
    t=s[1]=1;
    for (i=2;i<=n;i++) d[i]=oo;
    while (t)
    {
        x=s[1];
        s[1]=s[t--];
        p[s[1]]=1;
        p[x]=-1;
        down(1);
        for (i=first[x];i;i=next[i])
        {
            k=v[i];
            if (p[k]==-1) continue;
            if (!p[k])
            {
                s[++t]=k;
                p[k]=t;
            }
            if (d[k]>d[x]+w[i])
            {
                d[k]=d[x]+w[i];
                up(p[k]);
            }
        }
    }
}