暴動とルート
ある国に
n 個の都市があり、これらの都市をつなぐ道路が m 本あります。各道路には、現在発生している暴動の影響で通れる確率 (0 ≤ ≤ 1) が割り当てられています。都市自体は常に利用可能です。あなたの課題は、道路に割り当てられた確率を考慮しながら、都市 1 から都市 n までの道がすべて開通している確率を最大にするパスを探すことです。もし都市 1 から都市 n へのパスが存在しない場合は、その確率を 0 とみなします。都市
1 から都市 n までのパスが開通している確率の最大値を求めるプログラムを作成してください。入力
最初の行には、都市の数と道路の数を表す 2 つの整数
n と m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000) が空白区切りで与えられます。次の
m 行のそれぞれには、、、および (, ) が空白区切りで与えられます。これは、都市 と都市 を結ぶ道路と、その道路が開通している確率 を示しています。出力
都市
1 から都市 n までのパスが開通している確率の最大値を 1 つの実数として出力してください。正解との差が 1e-5 以内であれば正解とみなされます。例
入力 | 出力 |
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