F

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=5e5+10;
 5 const ll inf=0x3f3f3f3f3f3f3f3f;
 6 ll dis[25][maxn];
 7 ll vis[maxn];
 8 ll n,m;
 9 ll head[maxn],cnt,tot;
10 struct edge{
11     ll to,w,nxt;
12 }e[maxn];
13 
14 struct node{
15     ll v,dis;
16     bool operator < (const node &a) const{
17         return dis>a.dis;
18     }
19 }t,d;
20 
21 void add(ll u,ll v,ll w){
22     e[cnt].to=v;
23     e[cnt].w=w;
24     e[cnt].nxt=head[u];
25     head[u]=cnt++;
26 }
27 void dijstra(ll k){
28     memset(vis,0,sizeof(vis));
29     priority_queue<node>Q;
30     t.v=k;
31     t.dis=0;
32     Q.push(t);
33 
34     while(!Q.empty()){
35         if(vis[Q.top().v]){
36             Q.pop();
37             continue;
38         }
39         t=Q.top();
40         Q.pop();
41         ll u=t.v;
42         vis[u]=1;
43         dis[tot][u]=t.dis;
44         for(ll i=head[u];i!=-1;i=e[i].nxt){
45             ll y=e[i].to,w=e[i].w;
46             if( vis[y]==0 && dis[tot][y]>dis[tot][u]+w){
47                 dis[tot][y]=dis[tot][u]+w;
48                 d.v=y;
49                 d.dis=dis[tot][y];
50                 Q.push(d);
51             }
52         }
53     }
54     tot++;
55 }
56 
57 
58 
59 signed main()
60 {
61     memset(head,-1,sizeof(head));
62     memset(dis,0x3f,sizeof(dis));
63     cin>>n>>m;
64     for(ll i=0;i<m;i++){
65         ll u,v,w;
66         cin>>u>>v>>w;
67         add(u,v,w);
68         add(v,u,w);
69     }
70     tot=0;
71     ll ans=inf;
72     ll b[10];
73     ll a[10]={1,2,3,4,5,6,7,8,9};
74     dijstra(1);         //到自己一开始的最单路//dis[0][...]各点到1的距离
75     for(ll i=1;i<=7;i++){
76         cin>>b[i];      //龙珠位置
77         dijstra(b[i]);  //到龙珠的最短路//dis[1~7][...]各点到1~7个龙珠的最短路径
78     }
79     do{                 //用全排列求路径
80         ll now=dis[0][b[a[0]]];
81         now += dis[a[0]][b[a[1]]];
82         now += dis[a[1]][b[a[2]]];
83         now += dis[a[2]][b[a[3]]];
84         now += dis[a[3]][b[a[4]]];
85         now += dis[a[4]][b[a[5]]];
86         now += dis[a[5]][b[a[6]]];
87         ans = min(ans,now);
88     }while(next_permutation(a,a+7));
89     if( ans<inf ) cout<<ans<<endl;
90     else cout<<"-1"<<endl;
91     return 0;
92 }