P3371 【模板】单源最短路径(弱化版)
spfa作弊
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long LL;
const int N = 1e6+10, INF = 0x3f;
LL n, m, s;
LL h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
void spfa(){
memset(dist,INF,sizeof dist);
dist[s] = 0;
queue<LL> q;
q.push(s);
st[s] = true;
while(!q.empty()){
int t = q.front();
q.pop();
st[t] = false;
for(int i=h[t]; i!=-1; i=ne[i]){
int j = e[i];
if(dist[j] > dist[t]+w[i]){
dist[j] = dist[t]+w[i];
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m>>s;
while(m--){
int a, b, c;
cin>>a>>b>>c;
add(a,b,c);
}
spfa();
for(int i=1; i<=n; i++){
if(dist[i] == 1061109567) cout<<INT_MAX<<" ";
else cout<<dist[i]<<" ";
}
return 0;
}