1755: The New Game at Discoveryland

Discoveryland, a large amusement park in Dalian, recently launched a new entertainment item called “Passionate Swimming Lane”. Within the amusement facility, there are N joints and M swimming lanes. The swimming lane, which is one-way lane, goes from one joint to another. There might be several swimming lanes between two joints. And the swimming lane’s start joint and end joint can be the same joint. At each joint, a tourist’s probability of being crushed into a different lane is different. There is a weight for every swimming lane at a joint. The probability of being crushed into the lane equals to: the weight of the lane divided by the overall weights of all the lanes that the joint may lead to. The name of every joint consists of English letters or numbers. A tourist, who begins from the Joint named “start” and goes out of “end”, may experience many possible routes. In order to enhance the safety of the amusement facility, Manager Raven decides to reinforce the first K most likely routes that tourists may pass. Now, please help Raven to find out the respective probability of the K routes. If there are not that many routes, please output -1.

The first line of the input contains an integer T, which indicates the number of test cases. In the next row, there are three integers: N, M, K, representing the number of joints, number of swimming lanes and the first K routes required. 1 < N <= 100, 0 < M <= 10000, 1 < K <= 200 In the following M rows, each row has two strings (less than 12 characters) and one integer separated by space, the format of every row is: NAME1 NAME2 W, which means: at NAME 1, the weight of a tourist being crushed into NAME 2 is W. (W is an integer.)

K rows. For row i, the probability of the i-th most possible path ( 1 <= i <= K ). Keep 8 significant digits.

1
4 4 4
start LA 2
start Texas 2
LA end 1
Texas end 2

0.50000000
0.50000000
-1
-1

The probability of one path equals to the product of the probabilities of all the swimming lanes in the path. (题目有点问题，第一：输出为小数点后八位，而不是题目所说的八位有效数字。第二：每个样例后面要输出一个空行)