BF-优化-SPFA解法

#include<bits/stdc++.h>
using namespace std;
int n , m , w , x , y , z , s , t;
int d[2505] , vis[2505];
int a[5555][5555];
int main(){
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i = 1 ; i <= n ; i++){
        vis[i] = 0 , d[i] = 1e9;
    } 
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1; j <= n ; j++){
            a[i][j] = 1e9;
        }
    }
    for(int i = 1 ; i <= m ; i++){
        scanf("%d %d %d",&x , &y , &z);
        a[x][y] = z;
    }
    d[s] = 0; 
    vis[s] = 1;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = 1 ;i <= n ;i++){
            if(d[i] > d[u] + a[u][i]){
                d[i] = d[u] + a[u][i];
                if(!vis[i]){
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
    }
    cout << d[t] ;
}