Hunt

题目描述

There is a directed graph with $n$ vertices numbered from $1$ to $n$ and $m$ directed edges. You start at vertex $S$ and want to reach vertex $T$. The graph is strongly connected.

For each $1 \le i \le n$, vertex $i$ has a height $h_i$. For each $1 \le i \le m$, the $i$-th directed edge has a start vertex $u_i$, an end vertex $v_i$, and a length $d_i$. The time to traverse an edge from $u$ to $v$ is $C d \left(1 + \left(\dfrac{h_u - h_v}{d}\right)^2\right) + G (h_u^2 + h_v^2)$, where $C$ and $G$ are given constants.

You have a special item that can be used on at most $K$ edges. When used on an edge, the traversal time for that edge is divided by $\alpha$. That is, the time becomes $\dfrac{1}{\alpha}\left(C d \left(1 + \left(\dfrac{h_u - h_v}{d}\right)^2\right) + G (h_u^2 + h_v^2)\right)$, where $\alpha \ge 1$ is a given constant. You can also issue a secret command to change the height of at most one vertex to any real number. However, if your path passes through this vertex (i.e., it is an intermediate vertex on the path), the lengths of the edges immediately before and after it must be equal.

Find the minimum time required to reach vertex $T$ from vertex $S$.

输入格式

The first line of the input contains two integers $c$ and $t$, representing the test case number and the number of test cases. For the samples, $c$ indicates that the sample has the same constraints as test case $c$.

Then, for each test case:

• The first line contains eight integers $n, m, S, T, C, G, K, \alpha$, representing the number of vertices, the number of edges, the starting vertex, the target vertex, the constant $C$, the constant $G$, the maximum number of times the special item can be used, and the acceleration constant $\alpha$.

• The next line contains $n$ integers, the $i$-th of which is $h_i$, representing the current height of vertex $i$.

• The next $m$ lines each contain three integers $u, v, d$, representing the start vertex, end vertex, and length of an edge.

For all test cases, $1 \le n, m, \sum n \le 25000, \sum m \le 30000, 0 \le h_i, C, G, \alpha, d \le 1000000, 0 \le K \le 200, d \ge 1, \alpha \ge 1, 1 \le u, v, S, T \le n, u \not = v, S \not = T$.

It is guaranteed that for any vertex $t$, there is at least one simple path from $S$ to $T$.

输出格式

For each test case, output a single floating-point number on a single line, representing the answer. If the given answer is $ans$ and your answer is $res$, your answer is considered correct if $\frac{|\text{ans} - res|}{\max(1, \text{ans})} \le 10^{-8}$.

样例输入 #1

3 1
4 2 2 4 5 4 1 2
5 5 7 4
1 4 9
2 1 5

样例输出 #1

249.7777777778