Dijkstra+堆优化

#include<iostream>
#include<cstdio>

using namespace std;

int n,m,u,v,w,q;
int head[10001],next[200001],data[200001],value[200001];
int heap[10001],dis[10001];

void update(){
    int x,y;
    x=heap[1];
    y=head[x];
    while (y!=0){
        dis[data[y]]=min(dis[x]+value[y],dis[data[y]]);
        y=next[y];
    }
}

void adjust(int x){
    int p,minDis;
    p=x;
    minDis=dis[heap[x]];
    if (x*2<=n)
        if (dis[heap[x*2]]<minDis){
            p=x*2;
            minDis=dis[heap[x*2]];
        }
    if (x*2+1<=n)
        if (dis[heap[x*2+1]]<minDis){
            p=x*2+1;
            minDis=dis[heap[x*2+1]];
        }
    if (p!=x){
        swap(heap[x],heap[p]);
        adjust(p);
    }
}

void dijkstra(int x){
    int i,s=n;
    for (i=1;i<=n;i++)
        heap[i]=i;
    dis[1]=0;
    for (i=2;i<=n;i++)
        dis[i]=1111111111;
    while (s>0){
        update();
        swap(heap[1],heap[s]);
        s--;
        for (i=s/2;i>=1;i--)
            adjust(i);
    }
}

int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        next[i*2-1]=head[u],data[i*2-1]=v,value[i*2-1]=w,head[u]=i*2-1;
        next[i*2]=head[v],data[i*2]=u,value[i*2]=w,head[v]=i*2;
    }
    
    dijkstra(1);
    return 0;
}