[HAOI2009]旅行

Grade Open Time Friday, 19 September 2014, 10:04 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:04 am
Allow late Yes Close Time Friday, 26 September 2014, 10:04 am
Input file toura.in Output file toura.out
试题描述
小明住在城市1,而他的朋友小芳住在城市n。最近小明收到小芳的邀请,准备于近期赴约。可是由于最近下了很多暴雨,很多道路都被淹没。从城市1出发到城市n之间有很多小城镇,并且两个小城镇之间有一条直接道路相连。小明经过对近期天气和地形的科学分析,绘出了每条道路能顺利通行的概率。
为了能顺利到达目的地,请帮助小明找出一条最稳妥的路线,也就是从城市1出发到达城市n的路线中能顺利通行的最大概率。
输入数据
文件第一行包含两个整数nmn为城市数,m为道路条数。
接下来m行,每行包含三个整数abp ( 1<=p<=100 ),表示小城镇a与小城镇b间有一条道路,顺利通过这条道路的概率为p%
输出数据
一个实数P,为到达城市n的最大概率,P精确到小数点后6位。

样例输入
5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
样例输出
61.200000
样例说明:选择路线为1-4-3-5,概率为85%*90%*80%=61.2%
测试数据范围
30%的数据,n<=1000m<=3000
100%的数据,n<=10000m<=30000