AcWing 1135. Happy New Year (shortest path + search)

AcWing 1135. Happy New Year
A complicated problem , need DFS+ shortest path , First use spfa Find the shortest path from six starting points to the other points , Then search all the route plans of relatives , Find the minimum value and return

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int>PII;

#define x first
#define y second

const int N = 5e4 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int h[N], ne[M], e[M], w[M], idx;
int dist[6][N];  // Record six points （0+ Five relatives ） As the shortest path from the starting point to the other points 
bool st[N];
int source[6];

void add(int a, int b, int c){
    
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx ++ ;
} 

int dfs(int u, int start, int dis){
      // Accumulated search u A relative , From start A relative came , Cumulative expenses dis Time  
	if(u > 5) return dis;  // If you have searched all your relatives , Direct return 
	
	int res = INF;  // Initialize the distance value 
	for(int i = 1; i <= 5; i ++ ){
    
		if(!st[i]){
      // If this relative hasn't searched , Just search 
			int nest = source[i]; 
			st[i] = true;
			//dist[i][j] The record is from i Relatives left for j Distance of , therefore start No more conversion  
			res = min(res, dfs(u + 1, i, dis + dist[start][nest]));  
			st[i] = false;
		}
	} 
	return res;
}

void spfa(int start, int dist[]){
    
	memset(dist, 0x3f, N * 4);
	dist[start] = 0;
	memset(st, 0, sizeof st);
	
	priority_queue<PII, vector<PII>, greater<PII>>heap;  // Stack storage points and distances  
	heap.push({
    0, start});
	
	while(heap.size()){
    
		auto op = heap.top();
		heap.pop();
		
		int an = op.y;
		if(st[an]) continue;  // If this point is in the pile , Just skip it  
		st[an] = true;  // Mark this point in the heap  
		
		for(int i = h[an]; ~i; i = ne[i]){
    
			int j = e[i];
			if(dist[j] > dist[an] + w[i]){
    
				dist[j] = dist[an] + w[i];
				heap.push({
    dist[j], j});
			}
		} 
	}
}

int main()
{
    
	cin>>n>>m;
	source[0] = 1;
	memset(h, -1, sizeof h);
	for(int i = 1; i <= 5; i ++ ) cin>>source[i];
	
	while(m -- ){
    
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		add(b, a, c);
	}
	
	for(int i = 0; i <= 5; i ++ ){
    
		spfa(source[i], dist[i]);
	}
	
	memset(st, 0, sizeof st);
	cout<<dfs(1, 0, 0)<<endl;
	
	return 0;
}