NC21530. Accel World
描述
Chiaki was trapped in a strange place which can be regarded as a connected undirected graph with n vertices (numbered from 1 to n) and m weighted edges (numbered from 1 to m). In the beginning, Chiaki is at vertex 1 with speed v equals to 1 unit per second and would like to go to the vertex n.
There are some special vertices in the graph, called \textit{acceleration vertex}. Once Chiaki reached an acceleration vertex, her speed will be doubled: from v to 2v. The same acceleration vertex can be used multiple times to achieve multiple acceleration, but it only works under this limitation: the last acceleration vertex Chiaki visited should not equal to the current acceleration vertex Chiaki reached.
For example, vertex 2 and 3 are acceleration vertices while 1, 4 and 5 are not. If Chiaki chooses the path
, Chiaki's speed would be accelerated for three times (8 unit per second in the end). But if the path is 
, Chiaki would have only one acceleration.
Chiaki would like to know the minimum time needed to reach the vertex n.
There are some special vertices in the graph, called \textit{acceleration vertex}. Once Chiaki reached an acceleration vertex, her speed will be doubled: from v to 2v. The same acceleration vertex can be used multiple times to achieve multiple acceleration, but it only works under this limitation: the last acceleration vertex Chiaki visited should not equal to the current acceleration vertex Chiaki reached.
For example, vertex 2 and 3 are acceleration vertices while 1, 4 and 5 are not. If Chiaki chooses the path
Chiaki would like to know the minimum time needed to reach the vertex n.
输入描述
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains three integers n, m and k (2 ≤ n ≤ 100, 1 ≤ m ≤ 8000, 0 ≤ k ≤ n) -- the number of vertices, the number of edges and the number of special vertices.
Each of the following m lines contains three integers ui, vi and wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 1000) denoting an edge with wi unit length connecting ui and vi.
The next line contains k integers p1,p2,...,pk (1 ≤ pi ≤ n) denoting the index of each \textit{acceleration vertex}.
It's guaranteed that the sum of n over all test cases will not exceed 1000 and the sum of m over all test cases will not exceed 80000.
输出描述
For each test case, output a real number t denoting the minimum time to reach the vertex n and an integer s denoting the maximum times of acceleration Chiaki can achieve among all optimal solutions.
Your answer for t will be considered correct if and only if the absolute error or relative error of your answer is less than 10-8. And by the way, if s is greater than 32767, output ``Burst!'' (without the quotes) instead.
示例1
输入:
3 2 1 2 1 2 1 1 2 5 4 2 1 2 1 2 3 1 3 4 1 4 5 1 2 3 6 7 2 1 2 2 2 4 2 4 6 2 1 3 2 3 4 2 4 5 4 5 6 4 3 4
输出:
0.5000000000 2 2.0000000000 Burst! 3.5000000000 2