（未完待续）$\texttt{Dijkstra}$ 好题。

题目链接：Luogu P5304/LibreOJ 3087/BZOJ 5506/GXOI&GZOI2019 D2T2。

题目

题目描述

J 国有 $n$ 座城市，这些城市之间通过 $m$ 条单向道路相连，已知每条道路的长度。

一次，居住在 J 国的 Rainbow 邀请 Vani 来作客。不过，作为一名资深的旅行者，Vani 只对 J 国的 $k$ 座历史悠久、自然风景独特的城市感兴趣。

为了提升旅行的体验，Vani 想要知道他感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。

也许下面的剧情你已经猜到了——Vani 这几天还要忙着去其他地方游山玩水，就请你帮他解决这个问题吧。

多组数据，数据组数为 $T$。

数据范围

时空限制

题解

解法 A

其实是官方题解。

思路

假设答案是 $(a,b)$ 之间的最短路（$a,b$ 指在 $k$ 个数中的序号，不是节点编号），那么显然有 $a\ne b$，进一步地，$a$ 与 $b$ 间至少有 $1$ 个二进制位不同。

考虑枚举每一个二进制位 $t$，$t$ 这位为 $1$ 的算作集合 $A$，为 $0$ 的记作集合 $B$，集合 $A$ 向 $s$ 连一条零权边，集合 $B$ 向 $t$ 连一条零权边，求 $s$ 到 $t$ 的最短路，那么我们可以知道，答案一定在这些最短路中，找到最小的就是了。

代码

略。

解法 B

思路

最短路 + 染色。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll; //这道题要开 long long
#define INF 0X3F3F3F3F3F3F3F3F //正无穷
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=100000+5;
const int MAXM=500000+5;
const int MAXK=MAXN;

int n,m,K;
int id[MAXK];
int cnt,head[MAXN],to[MAXM],Next[MAXM];
ll w[MAXM];

inline void Add_Edge(reg int u,reg int v,reg ll len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}

struct Node{ //Dijkstra 存储用的结构体
    int id;
    ll dis;
    inline Node(reg int id=0,reg ll dis=0):id(id),dis(dis){
        return;
    }
    inline bool operator<(const Node& a)const{
        return dis<a.dis;
    }
    inline bool operator>(const Node& a)const{
        return dis>a.dis;
    }
};

bool vis[MAXN];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q; //优先队列

inline void Dijkstra(reg ll *dis,reg int *color){ //参数是两个数组，一个是 dis[] 距离，一个是 color[] 颜色
    memset(vis,false,sizeof(vis));
    for(reg int i=1;i<=n;++i)dis[i]=INF; //初始化距离
    while(!Q.empty())Q.pop();
    for(reg int i=1;i<=K;++i){ //K 个起点
        dis[id[i]]=0;
        color[id[i]]=id[i]; //染色
        Q.push(Node(id[i],0));
    }
    while(!Q.empty()){
        reg int ID=Q.top().id;
        Q.pop();
        if(vis[ID])
            continue;
        vis[ID]=true;
        for(reg int i=head[ID];i;i=Next[i])
            if(dis[to[i]]>dis[ID]+w[i]){
                dis[to[i]]=dis[ID]+w[i];
                color[to[i]]=color[ID]; //染色
                Q.push(Node(to[i],dis[to[i]]));
            }
    }
    return;
}

int X[MAXM],Y[MAXM],W[MAXM];
ll dis[2][MAXN];
int c[2][MAXN];

inline void Init(void){ //初始化
    cnt=0;
    memset(head,0,sizeof(head));
    return;
}

inline void Solve(void){
    n=read(),m=read(),K=read();
    for(reg int i=1;i<=m;++i)
        X[i]=read(),Y[i]=read(),W[i]=read();
    for(reg int i=1;i<=K;++i)
        id[i]=read();
    Init(); //别忘了初始化
    for(reg int i=1;i<=m;++i)
        if(X[i]!=Y[i])
            Add_Edge(X[i],Y[i],W[i]);
    Dijkstra(dis[0],c[0]);
    Init(); //别忘了初始化
    for(reg int i=1;i<=m;++i)
        if(X[i]!=Y[i])
            Add_Edge(Y[i],X[i],W[i]);
    Dijkstra(dis[1],c[1]);
    ll ans=INF;
    for(reg int i=1;i<=m;++i){ //求结果
        reg int x=X[i],y=Y[i],w=W[i];
        if(c[0][x]&&c[1][y]&&c[0][x]!=c[1][y])
            ans=min(ans,dis[0][x]+dis[1][y]+w);
    }
    printf("%lld\n",ans); //输出答案
    return;
}

int main(void){
    reg int T=read();
    while(T--)
        Solve(); //多组数据
    return 0;
}