#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=
100000+
10;
const int inf=
999999999;
int hade1[maxn],hade2[
20];
struct note
{
int next,e,w;
};
note a[2*maxn],b[
205];
int m,n,t,k,s,cnt,ans;
bool vis[maxn];
int dis[
20][maxn],p[
20];
void add1(
int s,
int e,
int w)
{
a[k].e=
e;
a[k].w=
w;
a[k].next=
hade1[s];
hade1[s]=k++
;
}
void add2(
int s,
int e,
int w)
{
b[k].e=
e;
b[k].w=
w;
b[k].next=
hade2[s];
hade2[s]=k++
;
}
void spfa(
int ss,
int n,
int *
dis)
{
memset(vis,0,
sizeof(vis));
for(
int i=
0;i<n;i++
)
dis[i]=
inf;
dis[ss]=
0;
queue<
int>
q;
q.push(ss);
while(q.size())
{
int st=
q.front();
q.pop();
vis[st]=
0;
for(
int i=hade1[st];i!=-
1;i=
a[i].next)
{
int ed=
a[i].e;
if(dis[ed]>dis[st]+
a[i].w)
{
dis[ed]=dis[st]+
a[i].w;
if(!
vis[ed])
{
vis[ed]=
1;
q.push(ed);
}
}
}
}
}
int dfs(
int st,
int len,
int n,
int cc)
{
vis[st]=
1;
int ans=
inf;
if(st==
0)
{
if(n==cc)
return len;
else return inf;
}
for(
int i=hade2[st];i!=-
1;i=
b[i].next)
{
int ed=
b[i].e;
if(!vis[ed]||ed==
0)
{
ans=min(ans,dfs(ed,len+b[i].w,n,cc+
1));
}
}
vis[st]=
0;
return ans;
}
int main()
{
scanf("%d",&
t);
while(t--
)
{
k=
0;
memset(hade1,-
1,
sizeof(hade1));
memset(hade2,-
1,
sizeof(hade2));
memset(p,0,
sizeof(p));
scanf("%d%d",&n,&
m);
for(
int i=
0;i<m;i++
)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&
z);
add1(x,y,z);
add1(y,x,z);
}
scanf("%d",&
s);
cnt=
0;
p[cnt++]=
0;
spfa(0,n,dis[
0]);
for(
int i=
0;i<s;i++
)
{
scanf("%d",&
p[cnt]);
spfa(p[cnt],n,dis[cnt]);
cnt++
;
}
k=
0;
for(
int i=
0;i<cnt;i++
)
for(
int j=
0;j<cnt;j++
)
if(i!=
j)
add2(i,j,dis[i][p[j]]);
ans=
inf;
for(
int i=
1;i<cnt;i++
)
{
memset(vis,0,
sizeof(vis));
vis[0]=
1;
ans=min(ans,dfs(i,dis[
0][p[i]],cnt,
1));
}
printf("%d\n",ans);
}
return 0;
}
转载于:https://www.cnblogs.com/Wangwanxiang/p/7363095.html
