A5853 | $「GXOI / GZOI2019」旅行者$

时间限制5s

内存限制512MB

通过 / 提交0/0

题目描述

J 国有 $n$ 座城市，这些城市之间通过 $m$ 条单向道路相连，已知每条道路的长度。 一次，居住在 J 国的 Rainbow 邀请 Vani 来作客。不过，作为一名资深的旅行者，Vani 只对 J 国的 $k$ 座历史悠久、自然风景独特的城市感兴趣。 为了提升旅行的体验，Vani 想要知道他感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。 也许下面的剧情你已经猜到了——Vani 这几天还要忙着去其他地方游山玩水，就请你帮他解决这个问题吧。

每个测试点包含多组数据，第一行是一个整数 $T$，表示数据组数。注意各组数据之间是互相独立的。 对于每组数据，第一行包含三个正整数 $n,m,k$，表示 J 国的 $n$ 座城市（从 $1 \sim n$ 编号），$m$ 条道路，Vani 感兴趣的城市的个数 $k$。 接下来 $m$ 行，每行包括 $3$ 个正整数 $x,y,z$，表示从第 $x$ 号城市到第 $y$ 号城市有一条长度为 $z$ 的单向道路。注意 $x,y$ 可能相等，一对 $x,y$ 也可能重复出现。 接下来一行包括 $k$ 个正整数，表示 Vani 感兴趣的城市的编号。

输出文件应包含 $T$ 行，对于每组数据，输出一个整数表示 $k$ 座城市之间两两最短路的最小值。

输入 #1

输出 #1

5
6

C++ 编辑器

输入

输出