Mission Impossible

I.M.F.(Impossible Missions Force) is a top secret spy organization in U.S. Ethan Hunt have serviced in this organization for many years. Now, he is retired and serves as a spy in a big company. Although he is very excellent, he would make mistakes. For example, last time he invaded another company to find some programming code. When he risked his life to steal the last few pages of the code, he found that all of the letters on them are only “}”. His boss is very angry. So, Ethan must finish this new mission and he needs your help.

In this new mission, Ethan successfully gets a big file in a computer and decided to send this file from this computer to his boss’s computer though the internet. We can assume the file is made of C small parts and Ethan could only send one part each unit time.

The network consists of n (n <= 200) computers, Ethan sits next to computer 1, his boss sits next to computer 2. There exists a probability p[i][j] between computer i and computer j, which means the probability of successfully transferring each part from i to j is p[i][j]. However, all of these links in the network are unidirectional (i.e. p[i][j] may be different from p[j][i]). We defined the e[i][j] as the expected time to send each part from i to j. For example, if p[i][j] = 10%， e[i][j] = 10 units.

You may find that the probability would be very tiny and the expected time could be very large since the route may be extremely long. Fortunately, Ethan knows that he has m teammates sit next to several computers. He can choose these computers as storage to shorten the transferring time. (i.e. each of the n computers could be used as node in any route, but only these m computers could be used as storages. Each attempt to send a small part, successful or unsuccessful, takes exactly one unite time, regardless of the number of links on the route.) So, he can do this mission as follows:

• Choose a computer which includes the file (i.e. C parts of information) as computer u.


• Choose another computer his boss or some teammate sits next to as computer v, and then takes time to transfer the file from u to v. If any part fails to be transferred, it will be resent immediately.


• When the file is sent to his boss’s computer, the mission is finished.

To satisfy his boss, Ethan must choose a route to make the total expected time from computer 1(the computer near him) to computer 2(the computer near his boss) minimum. You need to tell Ethan the minimum total expected time.

It is an impossible mission aha? Why not have a try. It’s easier than expected.

The first line contains an integer T, which means there are T test cases. Each test case is preceded by a blink line.

In each test case, you know n (2 <= n <= 200), which means the number of computers. Then an n*n matrix p(n) is following. p[i][j] means the probability of successfully transferring each part from i to j. You may assume that 0 <= p[i][j] <= 100.

Next line contains m (m <= n) means there are m computer that could serve as storage (i.e. the number of computers near Ethan, his teammates or his boss). Then a line contains m integer shows these computers. You may assume that it must contains computer 1 and computer 2.

The last line tells you there C parts in the big file. C is an integer which insure the answer is less than 1 000 000 000.

For each test case, you need to output a single line which contains the minimum expected time of the transfer when Ethan chooses the best way to finish his mission.

You’d better (not must) make the answer rounded to 7 decimal places. Your answer would be considered correct if each number has an absolute or relative error less than 10^-6.

2

5
0 1 20 0 0
0 0 0 0 0
0 0 0 50 90
0 20 0 0 0
0 0 0 90 0
3
1 2 5
10

4
0 100 0 0
100 0 100 0
0 100 0 100
0 0 100 0
0
1

111.111111
1.000000

2011 Multi-University Training Contest 16 - Host by TJU