
ZOJ Problem Set  4078
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 $1 \to 2 \to 3 \to 2 \to 5$, Chiaki's speed would be accelerated for three times ($8$ unit per second in the end). But if the path is $1 \to 2 \to 4 \to 2 \to 4 \to 2 \to 5$, Chiaki would have only one acceleration. Chiaki would like to know the minimum time needed to reach the vertex $n$. InputThere 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 \le n \le 100$, $1 \le m \le 8000$, $0 \le k \le n$)  the number of vertices, the number of edges and the number of special vertices. Each of the following $m$ lines contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 1000$) denoting an edge with $w_i$ unit length connecting $u_i$ and $v_i$. The next line contains $k$ integers $p_1,p_2,\dots,p_k$ ($2 \le p_i \le n  1$) 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$. OutputFor 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^{6}$. And by the way, if $s$ is greater than $32767$, output "Burst!" (without the quotes) instead. Sample Input3 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 Sample Output0.5000000000 2 2.0000000000 Burst! 3.5000000000 2 Author: LIN, Xi Source: Yet Another Xi Lin Contest 