PID700 / Formula 1
题目描述

F1,中文全称为一级方程式锦标赛,是最高级的方程式赛车比赛,现在你作为一名选手参加了一场F1的比赛,比较特殊地,本次比赛是在一个N个点M条边的无向图上举行的。

起点是S,终点是T,每条边长度为1公里,赛车每行驶1公里耗油1个单位,途中共有k个加油站,每经过加油站时,可以把油加满,但你的赛车设计顾问告诉你,油箱容量越大,赛车跑的就越慢。为了追求最快的速度,在能顺利到达终点,不会中途没油的前提下,你希望最小化油箱的容量(注意,虽然油箱变小可能导致路径变长,但我们只关心最小化的油箱)。

对于30%的数据,N<=200,M<=2000。

对于60%的数据,N<=1000,M<=10000。

对于100%的数据,1<=K,S,T<=N<=100000,1<=M<=150000,1<=T<=5。

输入格式

第一行一个正整数T表示测试数据组数,每组数据格式如下:

第一行三个整数,N,M,K,表示无向图的点数,边数,加油站数。

第二行K个正整数i1,i2..ik表示这些点上有加油站(可能重复,保证至少一个加油站在S点)。

接下来M行,每行两个正整数Bi,Ei表示有一条连接(Bi,Ei)的双向边(可能有重边和自环)。

最后一行两个正整数S,T表示起点、终点。

输出格式

对于每组数据,如果没法到达终点,输出-1,否则输出最小化的油箱容量。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论