Émeutes et Itinéraires
Dans un pays comptant
n villes, il existe m routes qui relient ces villes entre elles. Chaque route se voit attribuer une probabilité (0 ≤ ≤ 1) indiquant qu’elle reste ouverte malgré les émeutes en cours. Les villes, quant à elles, sont toujours accessibles. Votre objectif est de déterminer le chemin reliant la ville 1 à la ville n qui maximise la probabilité que l’ensemble de ce parcours soit ouvert, au regard des probabilités attribuées à chaque route. Si aucun chemin ne permet de rejoindre la ville 1 à la ville n, la probabilité est considérée égale à 0.Écrivez un programme qui trouve la probabilité maximale qu’un chemin reliant la ville
1 à la ville n demeure ouvert.Entrée
La première ligne contient deux entiers séparés par un espace,
n et m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000), qui représentent respectivement le nombre de villes et le nombre de routes.Les
m lignes suivantes contiennent chacune trois entiers séparés par des espaces, , , et (, ), décrivant une route reliant les villes et ainsi que la probabilité que cette route soit ouverte.Sortie
Affichez un seul nombre réel, correspondant à la probabilité maximale qu’un chemin reliant la ville
1 à la ville n reste ouvert. Votre réponse sera acceptée si elle diffère de la réponse correcte d’au plus 1e-5.Exemples
Entrée | Sortie |
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