Disturbios y Rutas
En un país con
n ciudades, existen m carreteras que conectan estas ciudades. A cada carretera se le asigna una probabilidad (0 ≤ ≤ 1) de encontrarse abierta debido a los disturbios en curso. Las ciudades en sí siempre están abiertas. Tu tarea es encontrar la ruta desde la ciudad 1 hasta la ciudad n que maximice la probabilidad de que todo el recorrido esté abierto, tomando en cuenta las probabilidades asignadas a cada carretera. Si no existe ninguna ruta entre la ciudad 1 y la ciudad n, se considera que la probabilidad es 0.Escribe un programa que calcule la probabilidad máxima de que exista un camino abierto desde la ciudad
1 hasta la ciudad n.Entrada
La primera línea contiene dos enteros separados por espacio,
n y m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000), que representan, respectivamente, el número de ciudades y el número de carreteras.Las siguientes
m líneas contienen tres números separados por espacio: , y (, ). Estos indican una carretera entre las ciudades y , y la probabilidad de que dicha carretera permanezca abierta.Salida
Imprime un único número real, que represente la probabilidad máxima de que haya un camino abierto desde la ciudad
1 hasta la ciudad n. Tu respuesta se aceptará si difiere de la respuesta correcta por como máximo 1e-5.Ejemplos
Entrada | Salida |
4 4
1 2 0.90
2 3 0.80
3 4 0.70
1 4 0.45 | 0.50400 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB