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 twoway 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:
20200116 20:41:30
An amazingly awesome problem, thanks for this! 

luka_dzimba911:
20180419 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 

ameya7:
20161010 09:35:50
Last edit: 20161010 13:59:45 

farhad chowdhury:
20160511 10:33:53
getting sigsegv can anybody plz provide me with some info or test cases 

(test):
20130801 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:
20130726 19:21:29
@Mehmet: Yes. The answer for that case is 0.062 

mehmetin:
20130726 17:23:54
2 2


Miguel Oliveira:
20130723 15:07:39
Ok, thanks for the quick replies. Accepted now :) 

Hector Navarro:
20130723 14:48:18
There was a mistake on the sample. It has been fixed 

Miguel Oliveira:
20130723 14:47:49
Sorry, I edited the post with another question, which is the reason for confusion. Please check the post again. 
Added by:  Hector Navarro 
Date:  20130722 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Local UCV 2013. Carlos Guía 