模板——SPFA

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int sta,ed,val,jump;
}a[1000005];
int n,m,jump[1000005],tot,line[1000005],point[1000005],judge[1000005];
void add(int sta,int ed,int val){
    tot++;
    a[tot].sta=sta;
    a[tot].ed=ed;
    a[tot].val=val;
    a[tot].jump=jump[sta];
    jump[sta]=tot;
}
void SPFA(int epos){
    int head=0,tail=1,pos;
    line[1]=epos;
    while(head!=tail){
        head++;
        if (head>1000000) head=1;
        pos=line[head];
        for (int i=jump[pos]; i; i=a[i].jump){
            if (point[pos]+a[i].val<point[a[i].ed]){
                point[a[i].ed]=point[pos]+a[i].val;
                if (!judge[a[i].ed]){
                    judge[a[i].ed]=1;
                    tail++;
                    if (tail>1000000) tail=1;
                    line[tail]=a[i].ed;
					if (point[line[head+1]]>point[line[tail]]) swap(line[head+1],line[tail]);
                }
            }
        }
        judge[pos]=0;
    }
}
int main(){
    memset(point,127,sizeof(point));
    scanf("%d%d",&n,&m);
    for (int i=1,x,y,z; i<=m; i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    SPFA(1);
    return 0;
}