记录编号	601112	评测结果	AAAAAAAAAAAA
题目名称	3109.[GXOI/GZOI2019]旅行者	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	3.411 s
提交时间	2025-06-02 16:58:59	内存使用	23.12 MiB

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5;
const int INF = 1e18;
int head[N],cnt;
int n,m,k;
struct edge{
    int v,w,next;
}e[M];
void addedge(int u,int v,int w){
    e[++cnt] = {v, w, head[u]};
    head[u] = cnt;
}
struct edg{int u,v,w;}ed[M];
int dis[3][N],vis[N],en[3][N],a[N];
struct node{
    int u, d;
    bool operator<(const node& r)const { 
		return d>r.d;
	}
};
void dij(int p){
    memset(vis,0,sizeof(vis));
    memset(dis[p],0x3f,sizeof(dis[p]));
    priority_queue<node> q;
    for(int i = 1;i<=k;i++){
        dis[p][a[i]]=0;
        en[p][a[i]]=a[i];
        q.push({a[i],0});
    }
    while(!q.empty()){
        int u = q.top().u; q.pop();
        if(vis[u]) continue; vis[u]=1;
        for(int i = head[u];i;i=e[i].next){
            int v=e[i].v,w=e[i].w;
            if(dis[p][v]>dis[p][u]+w){
                dis[p][v]=dis[p][u]+w;
                en[p][v]=en[p][u];
                q.push({v,dis[p][v]});
            }
        }
    }
}
signed main(){
	freopen("WAW.in","r",stdin);
	freopen("WAW.out","w",stdout);
    int _; scanf("%lld",&_);
    while(_--){
        scanf("%lld%lld%lld",&n,&m,&k);
        memset(head,0,sizeof(head));
        cnt=0;
        for(int i = 1;i<=m;i++){
            int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
            ed[i]={u,v,w};
            addedge(u,v,w);
        }
        for(int i = 1;i<=k;i++) scanf("%lld",&a[i]);
        dij(1);
        memset(head,0,sizeof(head));
        memset(e,0,sizeof(e));
        cnt = 0;
        for(int i = 1;i<=m;i++) 
        addedge(ed[i].v,ed[i].u,ed[i].w);
		dij(2);
        int ans = INF;
        for(int i = 1;i<=m;i++){
            int u=ed[i].u,v=ed[i].v,w = ed[i].w;
            if(en[1][u]&&en[2][v] && en[1][u] != en[2][v]) 
                ans = min(ans, dis[1][u] + dis[2][v] + w);
        }
        printf("%lld\n", ans);
    }
    return 0;
}