我还是太傻了
考虑每一条边的贡献，对于一条有向边\((u,v,w)\)，我们求出\(k\)个关键点中到\(u\)最近的距离\(dis_1\)，以及\(v\)到\(k\)个关键点中最近的距离\(dis_2\)，直接用\(dis_1+w+dis_2\)来更新答案就好了
所以正反两遍\(Dij\)就好
但是需要注意到一点，如果这两个点\(k\)个关键点中到\(u\)最近的点和\(v\)最近的·点相同，那么我们不能计入答案，因为这样只是走了一个环
代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=1e5+5;
const LL inf=9999999999999;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int st[maxn],n,m,K;
int X[maxn*5],Y[maxn*5],Z[maxn*5];
struct Shortest {
struct E{int v,nxt,w;}e[maxn*5];
int head[maxn],vis[maxn],g[maxn],num;LL d[maxn];
#define mp std::make_pair
typedef std::pair<LL,int> pii;
std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
inline void add(int x,int y,int z) {
e[++num].v=y;e[num].nxt=head[x];e[num].w=z;head[x]=num;
}
inline void clear() {
num=0;memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));
}
inline void Dij() {
for(re int i=1;i<=n;i++) d[i]=inf;
for(re int i=1;i<=K;i++) d[st[i]]=0,q.push(mp(0,st[i])),g[st[i]]=st[i];
while(!q.empty()) {
int k=q.top().second;q.pop();
if(vis[k]) continue;
vis[k]=1;
for(re int i=head[k];i;i=e[i].nxt)
if(d[e[i].v]>d[k]+e[i].w) {
d[e[i].v]=d[k]+e[i].w;g[e[i].v]=g[k];
q.push(mp(d[e[i].v],e[i].v));
}
}
}
}D[2];
int main() {
int T=read();
while(T--) {
D[0].clear(),D[1].clear();
n=read(),m=read();K=read();
for(re int x,y,z,i=1;i<=m;i++) {
x=read(),y=read(),z=read();
D[0].add(x,y,z);D[1].add(y,x,z);
X[i]=x,Y[i]=y,Z[i]=z;
}
for(re int i=1;i<=K;i++) st[i]=read();
D[0].Dij(),D[1].Dij();
LL ans=inf;
for(re int i=1;i<=m;i++)
if(D[0].g[X[i]]!=D[1].g[Y[i]])
ans=min(ans,D[0].d[X[i]]+Z[i]+D[1].d[Y[i]]);
printf("%lld\n",ans);
}
return 0;
}