好多多次最短路==，人工全排列了一下
#include<bits/stdc++.h> using namespace std; int ne,head[10010],n,m,a,b,c,k,ans=0x3f3f3f3f,vis[10010],d[10][10010],num[10],flg[10],bol[10010]; struct node{int to,nxt,dis;}eg[100100]; void adde(int u,int v,int c){eg[++ne].nxt=head[u];eg[ne].dis=c;eg[ne].to=v;head[u]=ne;} void spfa(int x) { memset(vis,0,sizeof(vis)); queue<int>q; q.push(num[x]);d[x][num[x]]=0;vis[num[x]]=1; while(!q.empty()) { int u=q.front();vis[u]=0;q.pop(); for(int i=head[u];i;i=eg[i].nxt) { int v=eg[i].to; if(d[x][v]>d[x][u]+eg[i].dis) {d[x][v]=d[x][u]+eg[i].dis; if(!vis[v]){q.push(v);vis[v]=1;}} } } } void cl(int zt) { int tag[10]; memset(tag,0,sizeof(tag)); for(int i=1;i<=k;i++) {tag[i]=zt%10;bol[num[tag[i]]]=1;zt/=10;} int tot=0,u=tag[1],v=tag[k]; for(int i=1;i<k;i++)tot+=d[tag[i]][num[tag[i+1]]]; int tk=0x3f3f3f3f; for(int i=1;i<=n;i++)if(!bol[i])tk=min(d[u][i]+d[v][i],tk); ans=min(ans,tot+tk); for(int i=1;i<=k;i++){bol[num[tag[i]]]=0;} } void dfs(int zt,int nod) { if(nod==k)cl(zt); else { for(int i=1;i<=k;i++) if(!flg[i]){flg[i]=1;dfs(zt*10+i,nod+1);flg[i]=0; } } } int main() { memset(d,0x3f,sizeof(d)); cin>>n>>m>>k; for(int i=1;i<=k;i++)cin>>num[i]; while(m--){cin>>a>>b>>c;adde(a,b,c);adde(b,a,c);} for(int i=1;i<=k;i++)spfa(i); dfs(0,0); cout<<ans; }