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.