lanqiao OJ 1366 spfa最短路

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
 
using namespace std ;
const long long INF = 0x3f3f3f3f3f3f3f3fLL ;
const int N = 5e3 + 10 ;
struct edge{
  int to ;
  long long w ;
  edge(int too , long long ww){
    to = too , w = ww ;
  }
};
int n , m , s ;
long long dis[N] ;
vector<edge> e[N] ;
bool inq[N] ; 
void spfa(int s){
  memset(dis,0x3f,sizeof(dis)) ;
  dis[s] = 0 ;
  queue<int> q ;
  q.push(s) ;
  inq[s] = 1 ;
  while(!q.empty()){
    int u = q.front() ;
    q.pop() ;
    inq[u] = 0 ;
    if(dis[u] == INF) continue ;
    for(int i = 0 ; i < e[u].size() ; i ++){
      int v = e[u][i].to ;
      long long w= e[u][i].w;
      if(dis[v] > dis[u] + w){
        dis[v] = dis[u] + w ;
        if(inq[v] == 0){
          q.push(v) ;
          inq[v] = 1 ;
        }
      }
    }
  }
}
int main(){
  cin >> n >> m >> s ;
  for(int i = 1 ; i <= m ; i ++){
    int a , b ;  
    long long c ;
    cin >> a >> b >> c ;
    e[a].push_back({b,c}) ;
    //e[b].push_back({a,c}) ;
  }
  spfa(s) ;
  for(int i = 1 ; i <= n ;i ++){
    if(dis[i] == INF) cout << "-1 " ;
    else printf("%lld ", dis[i]) ;
  }
}