P5377 旅行者
J 国有 座城市,这些城市之间通过 条单向道路相连,已知每条道路的长度。
一次,居住在 J 国的 Rainbow 邀请 Vani 来作客。不过,作为一名资深的旅 行者,Vani 只对 J 国的 座历史悠久、自然风景独特的城市感兴趣。
为了提升旅行的体验,Vani 想要知道他感兴趣的城市之间“两两最短路”的 最小值(即在他感兴趣的城市中,最近的一对的最短距离)。
也许下面的剧情你已经猜到了——Vani 这几天还要忙着去其他地方游山玩水,就请你帮他解决这个问题吧。
每个测试点包含多组数据,第一行是一个整数 ,表示数据组数。注意各组数据之间是互相独立的。
对于每组数据,第一行包含三个正整数 ,表示 J 国的 座城市(从 编号), 条道路,Vani 感兴趣的城市的个数 。
接下来 行,每行包括 个正整数 ,表示从第 号城市到第 号城市有一条长度为 的单向道路。注意 , 可能相等,一对 , 也可能重复出现。
接下来一行包括 个正整数,表示 Vani 感兴趣的城市的编号。
输出文件应包含 行,对于每组数据,输出一个整数表示 座城市之间两两最短路的最小值。
样例说明
对于第一组数据,1 到 3 最短路为 5;1 到 6 最短路为 7;3,6 无法到达,所以最近的两点为 1,3,最近的距离为 5。
对于第二组数据,1 到 2 最短路为 6;5 到 3 最短路为 6;其余的点均无法互相达,所以最近的两点为 1,2 和 5,3,最近的距离为 6。
数据规模与约定