// 最短路 Dijkstra 算法 O(mlogn)
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int N=50010,M=200010,INF=0x3f3f3f3f;
int h[N],to[M],w[M],ne[M],idx;
void add(int a,int b,int c){
  to[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m;
int num[6],d[6][N],vis[6],ans=INF;

void dijkstra(int s,int d[]){
  priority_queue<pii,vector<pii>,greater<pii>> q; //小根堆
  q.emplace(d[s]=0,s);
  while(!q.empty()){
    auto [dd,u]=q.top(); q.pop();
    if(dd>d[u]) continue; //这个u已经不是第一次出队了
    for(int i=h[u];i;i=ne[i]){
      int v=to[i];
      if(d[v]>d[u]+w[i]){
        d[v]=d[u]+w[i];
        q.emplace(d[v],v);
      }
    }
  }
}
void dfs(int step,int u,int dis){ //步数，当前点，距离和
  if(dis>ans) return; //剪枝
  if(step==5){
    ans=min(ans,dis); //走完亲戚 更新ans
    return;
  }
  for(int i=1;i<=5;i++)if(!vis[i]){ //枚举全排列，对所有可能的拜访顺序求距离和
    vis[i]=1; //标记
    dfs(step+1,i,dis+d[u][num[i]]);
    vis[i]=0; //回溯
  }
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m; //车站数目和公路的数目
  num[0]=1;  //佳佳的家在车站1
  for(int i=1;i<=5;i++) cin>>num[i]; //五个亲戚所在车站编号
  for(int i=0,a,b,c;i<m;i++){
    cin>>a>>b>>c;
    add(a,b,c),add(b,a,c);
  }
  
  memset(d,0x3f,sizeof(d));
  for(int i=0;i<=5;i++) dijkstra(num[i],d[i]); //对6个点跑最短路
  dfs(0,0,0); //爆搜答案
  cout<<ans;
}

让我来仔细梳理一下题目大意，以便大家更好的编写代码。

简化一下题意，就是佳佳要依次拜访五个亲戚，给出一张图及所有人的位置，求最短距离。

首先看，$n\leq50000$，说明搜索在这题是行不通的。

要我们求最短距离，那就来考虑一下最短路。

由于她是依次不间断拜访，即到达一家后立即前往下一家，所以我们首先可以以这$6$个点为起点依次跑最短路，得到以这$6$个点为起点的最短路径。换句话说，我们知道了每两个地方间的最短距离。

接着需要定的，就是拜访顺序了。

由于只有六处，且出发点已经固定，我们就可以考虑枚举全排列，将所有的可能的拜访顺序求出，同时将每个顺序的时间求出，去所有中的最小值即可。

大体思路并不难想，也就是这样，下面让我来分析一下代码细节：

$1.$有五处亲戚。为了便于编写，我们可以不按题面输出，有一个一维数组来存储。同时，因为起点佳佳家在$1$号点，所以我们可以在这个数组的第$6$个位置存入佳佳家，这样有利于编写。

$2.$此题更新数据后卡SPFA，所以只能采用堆优化dijkstra。

$3.$由于需要求解六处的最短路径，所以存最短路径时用一般的一维数组是肯定不行的。所以我们考虑使用二维数组，其中第一维可以存储出发的亲戚家的编号，第二维跟平时定义一样。

$4.$由于求最小值，所以枚举全排列时可以剪枝：当前用时已经大于过去最小值时，就可以return。

总体就是这样。

最后分析一下时间复杂度：枚举全排列时间不大，主要在计算最短路上。采用堆优化dijkstra后，耗时为：$O(m\log n)$（常数忽略不计）

$AC$ $Code$

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
#define _rep(i, a, b) for (int i=(a); i<(b); i++)
using namespace std;

typedef pair<int, int> P;
const int MAXN = 50010, INF = 1e9;

struct edge {
	int to, cost;
};
std::vector<edge> G[MAXN];
void addedge(int u, int v, int c) {
	G[u].push_back((edge){v, c});
	G[v].push_back((edge){u, c});
}//建无向边操作

int n, m, rel[7], d[7][MAXN], ans = INF;//记得ans要赋INF，以及d数组要开二维
bool vis[7];

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > q;
	d[s][rel[s]] = 0;
	q.push(P(0, rel[s]));
	while (!q.empty()) {
		P p = q.top();
		q.pop();
		int v = p.second;
		if (p.first > d[s][v]) continue;
		_rep (i, 0, G[v].size()) {
			edge e = G[v][i];
			if (d[s][e.to] > d[s][v]+e.cost) {
				d[s][e.to] = d[s][v]+e.cost;
				q.push(P(d[s][e.to], e.to));
			}
		}
	}
}//标准堆优化dijkstra

void dfs(int cur, int cost, int pos) {
	if (cost > ans) return ;
	if (cur == 5) {
		ans = min(ans, cost);
		return ;
	}
	_for (i, 1, 5) 
		if (!vis[i]) {
			vis[i] = true;
			dfs(cur+1, cost+d[pos][rel[i]], i);
			vis[i] = false;
		}
}//标准枚举全排列

int main() {
	cin >> n >> m;
	_for (i, 1, 5) cin >> rel[i];
	_for (i, 1, m) {
		int u, v, c;
		cin >> u >> v >> c;
		addedge(u, v, c);
	}//建图
	rel[6] = 1;
	memset(d, 0x3f, sizeof(d));//记得d数组要初始化
	_for (i, 1, 6) dijkstra(i);
	dfs(0, 0, 6);
	cout << ans << endl;
	return 0;//完结撒花
}