UCV2013K - Zombie Outbreak


As many books, movies and video games had shown us, a zombie outbreak was inevitable. However, all hope is not lost. As usual you've encountered a young girl that has been bitten but not transformed. Therefore, you've escorted her to a medial facility so her blood can be studied and a cure manufactured.

Unfortunately, the medical facility, for obvious reasons, has not been resupplied in a while. The scientists there have asked you to pick several tools, viruses and whatnots, from N places in the city.

Now that you have to go out again, you have created a map with the N + 1 locations: the medical facility (location 0) and the other N where the scientists need you to pick something up (numbered from 1 to N). You've also came up with M two-way paths between some of the locations and the probability to encounter a zombie pack on each of those paths. Note that this is isn't science fiction. If you encounter a zombie pack, you will not survive.

You certainly want to fetch all the items and come back alive. You want to compute the maximal probability of picking every item and coming back to the medical facility (safe and sound) if you take a closed walk (cycle that allows node repetitions).

Input

The input contains several test cases. Each test case begins with two integers, the number of places you have to go to (1 <= N <= 16) and the number of paths you came up with (1 <= M <= N^2), separated by a single space.

The next M lines contain 2 integers and a real number separated by spaces. Two integers ui and vi (0 <= ui, vi <= N and ui<>vi) are the locations this path connects. Real number pi (0 <= pi <= 1) represents the probability that you will encounter a zombie pack along this path.

You may assume that, for all i <> j, probabilities pi and pj are independent from each other.

The end of input is indicated by a test case with N = M = 0 and should not be processed

Output

For each test case output a single line with a single real number: the probability of getting back to the medical facility alive with all items. Round the result to exactly three places after decimal point. If there's no way to pick all items, you should output 0.000.

Example

Input:
2 3
0 1 0.3
0 2 0.4
1 2 0.2
2 3
0 1 0.3
0 2 0.5
1 2 0.1
2 2
0 1 0.1
0 1 0.9
2 3
0 1 0.92
0 2 0.92
1 2 0.92
2 3
0 1 0.92
0 2 0.92
1 2 0.93
0 0 Output: 0.336
0.397
0.000
0.001
0.000

hide comments
sandeepd: 2020-01-16 20:41:30

An amazingly awesome problem, thanks for this!

luka_dzimba911: 2018-04-19 23:14:30

Im amazed how good this problem was very satisfying ,i noticed they can input same connections twice or more that gave me WA

farhad chowdhury: 2016-05-11 10:33:53

getting sigsegv can anybody plz provide me with some info or test cases

(test): 2013-08-01 10:35:01

@Hector: The exact value for the test case from Mehmet is 0.0625. When rounded, it should be 0.063, shouldn't it?

Hector Navarro: 2013-07-26 19:21:29

@Mehmet: Yes. The answer for that case is 0.062

mehmetin: 2013-07-26 17:23:54

2 2
0 1 0.5
0 2 0.5

Is the answer 0.062 or 0.063?
My output gives 0.062 when I use printf("%.3f",ans). (Which should be 0.063 according to problem description)
Also, is the input given to at most 3 significant digits?

Last edit: 2013-07-26 17:38:28
Miguel Oliveira: 2013-07-23 15:07:39

Ok, thanks for the quick replies. Accepted now :)

Hector Navarro: 2013-07-23 14:48:18

There was a mistake on the sample. It has been fixed

Miguel Oliveira: 2013-07-23 14:47:49

Sorry, I edited the post with another question, which is the reason for confusion. Please check the post again.

Carlos Guía: 2013-07-23 14:47:49

@Miguel,

Nice questions, specially #2. However, the answer of both questions can be found analyzing sample case #2, so I'll let you do that before giving more details.

Last edit: 2013-07-23 14:31:52

Added by:Hector Navarro
Date:2013-07-22
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local UCV 2013. Carlos Guía