这题因为排列有很多种，我们最简单的想法是对所有的排列进行最短路，但是这样复杂度不行
因此我们可以先跑6次最短路，之后用一次dfs来求取答案
#include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<algorithm> using namespace std; typedef pair<int,int> PII; const int N=2e5+10; int n,m; int s[7]; int e[N],ne[N],w[N],h[N],idx; int st[N]; int dis[6][50010]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dijkstra(int a){ memset(dis[a], 0x3f,sizeof dis[a]); dis[a][s[a]] = 0; memset(st, 0, sizeof st); priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, s[a]}); while (heap.size()){ auto t = heap.top(); heap.pop(); int ver = t.second; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; ~i; i = ne[i]){ int j = e[i]; if (dis[a][j] > dis[a][ver] + w[i]) { dis[a][j] = dis[a][ver] + w[i]; heap.push({dis[a][j], j}); } } } } int dfs(int cur,int x,int d){ if(cur==6) return d; int i; int res=0x3f3f3f3f; for(i=1;i<=5;i++){ if(!st[i]){ int j=s[i]; st[i]=1; res=min(res,dfs(cur+1,i,d+dis[x][j])); st[i]=0; } } return res; } int main(){ cin>>n>>m; s[0]=1; memset(h,-1,sizeof h); for(int i=1;i<=5;i++){ scanf("%d",&s[i]); } int i; while(m--){ int u,v,x; scanf("%d%d%d",&u,&v,&x); add(u,v,x); add(v,u,x); } for(int i=0;i<=5;i++){ dijkstra(i); } memset(st,0,sizeof st); int res=dfs(1,0,0); cout<<res<<endl; }