当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3994:Mission Impossible

Special Judge 特殊评判
题目描述
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
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-3994

最后修改于 2020-10-25T23:09:06+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
30000/10000MS(Java/Others) 65536/65536K(Java/Others)