CHICAGO  106 miles to Chicago
In the movie "Blues Brothers", the orphanage where Elwood and Jake were raised may be sold to the Board of Education if they do not pay 5000 dollars in taxes at the Cook County Assessor's Office in Chicago. After playing a gig in the Palace Hotel ballroom to earn these 5000 dollars, they have to find a way to Chicago. However, this is not so easy as it sounds, since they are chased by the Police, a country band and a group of Nazis. Moreover, it is 106 miles to Chicago, it is dark and they are wearing sunglasses.
As they are on a mission from God, you should help them find the safest way to Chicago. In this problem, the safest way is considered to be the route which maximises the probability that they are not caught.
Input Specification
The input file contains several test cases.
Each test case starts with two integers n and m (2 ≤ n ≤ 100 , 1 ≤ m ≤ n*(n1)/2). n is the number of intersections, m is the number of streets to be considered.
The next m lines contain the description of the streets. Each street is described by a line containing 3 integers a, b and p (1 ≤ a, b ≤ n , a ≠ b, 1 ≤ p ≤ 100): a and b are the two end points of the street and p is the probability in percent that the Blues Brothers will manage to use this street without being caught. Each street can be used in both directions. You may assume that there is at most one street between two end points.
The last test case is followed by a zero.
Output Specification
For each test case, calculate the probability of the safest path from intersection 1 (the Palace Hotel) to intersection n (the Honorable Richard J. Daley Plaza in Chicago). You can assume that there is at least one path between intersection 1 and n.
Print the probability as a percentage with exactly 6 digits after the decimal point. The percentage value is considered correct if it differs by at most 10^{6} from the judge output. Adhere to the format shown below and print one line for each test case.
Sample Input
5 7 5 2 100 3 5 80 2 3 70 2 1 50 3 4 90 4 1 85 3 1 70 0
Sample Output
61.200000 percent
The safest path for the sample input is 1 > 4 > 3 > 5
hide comments
code_astra1:
20160205 11:03:47
Guys please don't forget to print "percent" along with the answer it is not there for clarity it is there to be printed!


dhumketu:
20160123 18:26:01
For those who are wondering how to calc. percentages, 61.200000 = 85(1>4)*90(4>3)*80(3>5). 

Abhinandan Agarwal:
20150725 19:44:41
Use the property of multiplicity of probabilities! 

tarunsai:
20150628 07:16:35
how do we calculate percentage


MKM:
20150623 16:39:22
the percent changes the logic a bit :D 

bholagabbar:
20150421 17:10:12
Alright so tried converting this to the 'longest path problem' using Dijisktra. I greedily obtain the longest path. My answer for the above problem = 255 matches the path taken above. 255 is the sum of paths between 1 > 4 > 3 > 5.


Vishesh Raimugia:
20150302 18:36:52
Beware, more than 1 test case, I forgot!! 

humble_coder:
20150212 12:38:34
yaa the 'percent' word is too mischievous.. 

lovecode:
20150205 19:02:03
good problem for beginners try to do using both Dijsktra and Floyd's warshall


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150104 22:30:34
O(n^3) vs O(n^2) based on my experiment

Added by:  Adrian Kuegel 
Date:  20050624 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 
Resource:  University of Ulm Local Contest 2005 