AcWing 1135. 新年好 题解（最短路+搜索）

AcWing 1135. 新年好
比较复杂的一道题，需要DFS+最短路，先用spfa找出六个起点到其余个点的最短路，再暴搜所有走亲戚的路线方案，找到最小值返回

#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];  //记录六个点（0+五个亲戚）作为起点到其余个点的最短路径
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){
      //累积搜了u个亲戚，从第start个亲戚走来的，累积花费dis时间 
	if(u > 5) return dis;  //如果已经搜完所有亲戚，直接返回结果
	
	int res = INF;  //初始化距离值
	for(int i = 1; i <= 5; i ++ ){
    
		if(!st[i]){
      //如果这个亲戚没搜过，就搜索
			int nest = source[i]; 
			st[i] = true;
			//dist[i][j]记录的是从第i个亲戚家出发到j的距离，所以start不用再转化 
			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;  //用堆储存点和距离 
	heap.push({
    0, start});
	
	while(heap.size()){
    
		auto op = heap.top();
		heap.pop();
		
		int an = op.y;
		if(st[an]) continue;  //如果这个点在堆内，就直接跳过 
		st[an] = true;  //标记这个点在堆内 
		
		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;
}