Rivolte e Percorsi
In un paese con
n città, ci sono m strade che le collegano. A ciascuna strada è associata una probabilità (0 ≤ ≤ 1) di essere aperta a causa di rivolte in corso. Le città invece rimangono sempre aperte. Il tuo compito è trovare il percorso dalla città 1 alla città n che massimizza la probabilità che l’intero percorso sia aperto, tenendo conto delle probabilità assegnate a ogni strada. Se non esiste alcun percorso dalla città 1 alla città n, la probabilità è considerata 0.Scrivi un programma che trovi la probabilità massima che un percorso dalla città
1 alla città n sia aperto.Input
La prima riga contiene due interi separati da spazio,
n e m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000), che rappresentano il numero di città e il numero di strade, rispettivamente.Le successive
m righe contengono ciascuna tre interi separati da spazio , e (, ), che indicano una strada tra le città e , e la probabilità che quella strada sia aperta.Output
Stampa un unico numero reale, che rappresenta la probabilità massima che un percorso dalla città
1 alla città n sia aperto. La tua risposta sarà accettata se differirà dalla risposta corretta di al massimo 1e-5.Esempi
Input | Output |
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