eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Adventures

Adventures

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Everyone knows about the travel history of Indiana Jones. As usual, in search of adventure, Jones gets into a difficult situation. Now he is in an ancient Indian temple. In the hall of the temple on the wall painted a map of the temple. The temple is a lot of rooms connected by passageways, are designed so that it can pass through in one direction only. According to chronicles aware that if the go through all the rooms, or if someone finds a treasure, the temple destroyed, and it can be to escape to freedom. Also know that if you enter and exit from any room, the ceiling in this room boned, and pass through this room in the future is impossible. The map identifies all church rooms and the tunnels between them, long lines and tunnels, as well as the probability that a certain room will be located treasure Indiana lazy likes all people, and he asked to solve the problem. It is necessary to minimize the average expected path traversed by tunnels. He also reported that can teleport to any room. You have to find a way in which we get the minimum expected distance, with all rooms. If there is no way of containing all the rooms has to inform the Jones, because in this case, perhaps the fact that Jones did not return from the temple.

The input file contains several test. Each test is a map of the temple. In the first line of each test record number 1  N  100 - number of rooms in the temple. After come the N lines of N aij numbers in each (|aij| < 1000). If the line i at position j aij record number this means that the room i to room j is the tunnel length aij. If aij number less than zero, this means that the tunnel is overwhelmed, and it is impossible to pass. After following is one line containing N number pi. The number pi is the probability that room number is i will treasure. The last test has N = 0 and is not processed. For each test case to print the average distance with three characters after the dot. If there is no way of containing all the rooms, put -1.

Приклад

Вхідні дані #1
4
1 1 -1 -1
-1 1 2 -1
-1 -1 1 3
-1 -1 -1 1
0.1 0.7 0.3 0.4
3
1 1 -1
-1 1 -1
-1 1 1
0.1 0.2 0.3
0
Вихідні дані #1
2.947
-1