最短路算法与dfs的结合,首先预处理出这六家到其他点的最短路,然后从起点开始dfs爆搜用时最短的方案,此题会卡spfa,因此使用堆优化的dijkstra。注意dfs的手法
//最短路算法与dfs结合
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=50010, M=2e5+10;
int h[N],e[M],w[M],ne[M],idx;
int dist[6][N],q[N],n,m,id[6];
bool st[N],dst[N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int k){
int tmp[N];
memset(tmp,0x3f,sizeof tmp);
memset(st,0,sizeof st);
tmp[id[k]]=0;
int tt=1,hh=0;
q[0]=id[k];
st[id[k]]=true;
while(tt!=hh){
int t=q[hh++];
if(hh==N) hh=0;
st[t]=false;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(tmp[j]>tmp[t]+w[i]){
tmp[j]=tmp[t]+w[i];
if(!st[j]){
st[j]=true;
q[tt++]=j;
}
}
}
}
for(int i=1;i<=n;i++)
dist[k][i]=tmp[i];
}
void dijkstra(int k){
int tmp[N];
memset(tmp,0x3f,sizeof tmp);
memset(st,0,sizeof st);
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,id[k]});
tmp[id[k]]=0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int d=t.first,ver=t.second;
if(!st[ver]){
st[ver]=true;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(tmp[j]>d+w[i]){
tmp[j]=d+w[i];
heap.push({tmp[j],j});
}
}
}
}
for(int i=1;i<=n;i++)
dist[k][i]=tmp[i];
}
int dfs(int u,int start,int dis){
if(u==6) return dis;
int res=0x3f3f3f3f;
for(int i=1;i<6;i++){
if(!dst[i]){
int nxt =id[i];
dst[i]=true;
res = min(res,dfs(u+1,i,dis+dist[start][nxt]));
dst[i]=false;
}
}
return res;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
id[0]=1;
for(int i=1;i<6;i++) cin>>id[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++){
dijkstra(i);
}
//找访问顺序
int t=dfs(1,0,0);
cout<<t<<endl;
return 0;
}