【acwing】1135. 新年好***（dijkstra+堆优化）

穿越隧道

预处理，再搜索出最小的答案。
$mlo{g}_n$ + $5!$

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N = 5e4 + 10, M = 4e5 + 10, INF = 0x3f3f3f3f;
int n,m;
int source[6];
int h[N],e[M],w[M],ne[M],idx;
int q[N],dis[6][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 heap_dij(int start, int dis[]){
    
	memset(dis,0x3f, N * 4);//之所以不用sizeof(dis),因dis此时为二维数组
	dis[start] = 0;
	memset(st,0,sizeof(st));
	priority_queue<pii, vector<pii>,greater<pii>> heap;
	heap.push({
    0,start});
	while(heap.size()){
    
		pii t = heap.top();
		heap.pop();
		int ver = t.second;
		if(st[ver]) continue;
		st[ver] = true;
		for(int i = h[ver]; i!= -1; i = ne[i]){
    
			int j = e[i];
			if(dis[j] > dis[ver] + w[i]){
    
				dis[j] = dis[ver] + w[i];
				heap.push({
    dis[j],j});
			}
		}
	}
}
int dfs(int u, int start, int dist){
    
	if(u == 6) return dist;
	int res = INF;
	for(int i = 1; i <= 5; i++){
    //五个亲戚
		if(!st[i]){
    
			int next = source[i];
			st[i] = true;
			res = min(res,dfs(u + 1,i,dist + dis[start][next]));
			st[i] = false;
		}
	}
	return res;
} 
int main(){
    
	
	scanf("%d%d",&n,&m);
	source[0] = 1;
	memset(h,-1,sizeof(h));
	for(int i = 1; i <= 5; i++) scanf("%d",&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 < 6; i++){
    
		heap_dij(source[i],dis[i]);
	}
	memset(st,0,sizeof(st));
	printf("%d\n",dfs(1,0,0));//拜访第一个亲戚，当前起点为source0,总距离0. 
	return 0;
}