新年好~

思路：
预处理，求六遍dijkstra，处理出1,a,b,c,d,e到图中各点的单源最短路。
然后枚举所有从1出发的方案，比如1->a->c->d->b->e就是其中之一，将这些方案的路径和求个最小值即可（已经在预处理中解决了路径问题）。 而在这一步中，可以用dfs，也可以直接用STL中的next_permutation来解决。

代码出现的变量等数据解释：
id[x] 表示下标为 $x$ 的点编号，我们规定id[1]=1，在样例中，id[x]恰好为x。
d[x][] 表示从相应下标 $x$ 对应的点出发到其他点的单源最短路。
dijk(int st,int dist[]) st表示源点的id。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=5e4+5, M=1e5+5;
const int INF=0x3f3f3f3f;

int head[N],tot;
struct node{
    int to,w,next;
}e[M<<1];
void add(int u,int v,int w){e[tot].to=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;}
int n,m;
int id[7];
int d[7][N];

void dijk(int st,int dist[]){
    bool vis[N]={0};
    dist[st]=0;

    priority_queue<PII,vector<PII>,greater<PII>> pque;
    pque.push({0,st});

    while(pque.size()){
        auto hd=pque.top(); pque.pop();

        int ver=hd.second;
        if(vis[ver]) continue;
        vis[ver]=true;

        for(int i=head[ver];~i;i=e[i].next){
            int go=e[i].to;
            if(dist[go]>dist[ver]+e[i].w){
                dist[go]=dist[ver]+e[i].w;
                pque.push({dist[go],go});
            }
        }
    }
}

int main(){
    memset(head,-1,sizeof head);
    memset(d,0x3f,sizeof d);
    cin>>n>>m;

    id[1]=1;
    for(int i=2;i<=6;i++) cin>>id[i];

    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w); add(v,u,w);
    }

    for(int i=1;i<=6;i++) dijk(id[i],d[i]);

    int a[7];
    for(int i=1;i<=6;i++) a[i]=i;
    int ans=INF;
    do{
        int rec=0;
        rec+=d[a[1]][id[a[2]]];
        for(int i=2;i<=5;i++) rec+=d[a[i]][id[a[i+1]]];
        ans=min(ans,rec);
    }while(next_permutation(a+2,a+1+6));

    cout<<ans<<endl;

    return 0;
}