AcWing 1129. 热浪 题解（最短路—spfa）

AcWing 1129. 热浪
SPFA求最短路的，找到单源最短路，就是建立一个队列，按照图中的路径遍历，将更新过找到最短路径的点加入队列中，然后将队列中的元素依次出队，按照出队元素在图中继续遍历，最终找到最短路

#include<bits/stdc++.h>

using namespace std;

const int N = 7000;

int e[N * 2], ne[N * 2], h[N], w[N * 2], idx;
int T, C, S, E;
int dist[N];
bool st[N];
int q[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, 0x3f, sizeof dist);
	dist[S] = 0;
	
	int hh = 0, tt = 1;
	q[0] = S;
	st[S] = true;
	
	while(hh != tt){
    
		int t = q[hh ++ ];
		if(t == N) hh = 0;  //如果遍历到最后一个点了 
		st[t] = false;
		
		for(int i = h[t]; ~ i; i = ne[i]){
    
			int j = e[i];
			if(dist[j] > dist[t] + w[i]){
    
				dist[j] = dist[t] + w[i];
				if(!st[j]){
    
					q[tt ++ ] = j;
					st[j] = true;
					if(j == N) tt = 0;				
				}
			}
		}
	}
}

int main()
{
    
	cin>>T>>C>>S>>E;
	memset(h, -1, sizeof h);
	for(int i = 0; i < C; i ++ ){
    
		int a, b, c;
		cin>>a>>b>>c;
		add(a, b, c);
		add(b, a, c);
	}
	
	spfa();
	
	cout<<dist[E]<<endl;
	
	return 0;
}