spfa模板

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define v first
#define w second
using namespace std;
const int N = 510;
typedef pair<int,int> pii;
vector<pii> E[N];
int inq[N],d[N];
int n,m;

int main(){
    cin>>n>>m;
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        E[a].push_back({b,c});
    }

    memset(d,0x3f,sizeof d);
    memset(inq,0,sizeof inq);

    queue<int> q;
    q.push(1);
    d[1]=0;
    inq[1]=1;
    while(q.size()){
        int now=q.front();
        q.pop();
        inq[now]=0;

        for(int i=0;i<E[now].size();i++){

            int vv=E[now][i].v;
            if(d[vv]>d[now]+E[now][i].w){

                d[vv]=d[now]+E[now][i].w;

                if(inq[vv]) continue;

                inq[vv]=1;

                q.push(vv);

            }

        }
    }

    cout<<(d[n]!=0x3f3f3f3f?d[n]:-1);
}