分析
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e17+7;
int d[100100],head[100100],nxt[1000100],to[1000100],w[1000100],cnt;
int x[500100],y[500100],z[500100],n,m,s,t,pos[100100],vis[100100];
inline void add(int x,int y,int z){
nxt[++cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
w[cnt]=z;
}
priority_queue<pair<int,int> >q;
inline int dij(){
memset(vis,0,sizeof(vis));
for(int i=1;i<=t;i++)d[i]=inf;
d[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=nxt[i])
if(d[to[i]]>d[x]+w[i]){
d[to[i]]=d[x]+w[i];
q.push(make_pair(-d[to[i]],to[i]));
}
}
return d[t];
}
signed main(){
int T,i,j,k;
scanf("%lld",&T);
while(T--){
int ans=inf;
scanf("%lld%lld%lld",&n,&m,&k);
for(i=1;i<=m;i++)scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
s=n+1,t=n+2;
for(i=1;i<=k;i++)scanf("%lld",&pos[i]);
for(i=0;i<=17;i++){
cnt=0;
memset(head,0,sizeof(head));
for(j=1;j<=m;j++)add(x[j],y[j],z[j]);
for(j=1;j<=k;j++)
if((1<<i)&pos[j]){
add(s,pos[j],0);
}else {
add(pos[j],t,0);
}
ans=min(ans,dij());
cnt=0;
memset(head,0,sizeof(head));
for(j=1;j<=m;j++)add(x[j],y[j],z[j]);
for(j=1;j<=k;j++)
if(!((1<<i)&pos[j])){
add(s,pos[j],0);
}else {
add(pos[j],t,0);
}
ans=min(ans,dij());
}
printf("%lld
",ans);
}
return 0;
}