Unruhen und Routen
In einem Land mit
n Städten gibt es m Straßen, die diese Städte miteinander verbinden. Jede Straße besitzt eine Wahrscheinlichkeit (0 ≤ ≤ 1), dass sie aufgrund anhaltender Unruhen passierbar ist. Die Städte selbst bleiben jedoch immer zugänglich. Deine Aufgabe besteht darin, den Weg von Stadt 1 nach Stadt n zu finden, bei dem die Gesamtwahrscheinlichkeit, dass alle verwendeten Straßen offen sind, am größten ist. Falls es keinen Weg von Stadt 1 nach Stadt n gibt, wird die Wahrscheinlichkeit als 0 angesehen.Schreibe ein Programm, das die maximale Wahrscheinlichkeit eines passierbaren Pfads von Stadt
1 nach Stadt n berechnet.Eingabe
Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen
n und m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000). Diese stehen für die Anzahl der Städte bzw. die Anzahl der Straßen.In den folgenden
m Zeilen stehen jeweils drei durch Leerzeichen getrennte Werte , und (, ). Sie geben an, zwischen welchen Städten und eine Straße verläuft und wie hoch die Wahrscheinlichkeit ist, dass diese Straße offen ist.Ausgabe
Gib eine einzelne Fließkommazahl aus, welche die maximale Wahrscheinlichkeit eines passierbaren Pfads von Stadt
1 nach Stadt n angibt. Die Antwort wird akzeptiert, wenn sie vom korrekten Ergebnis höchstens um 1e-5 abweicht.Beispiele
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