e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Dijkstra algorithm

Çikaqoya qədər 106 mil

"Blyuz qardaşları" filmində, Elvud və Cekin tərbiyə aldıqları uşaq evi, əgər onlar Kukun Çikaqodakı ofisinə 5000 dollar vergi ödəməsələr, Təhsil Şurasına satılmalıdır. Onlar Palas Oteldə konsert verməklə 5000 dollar qazanaraq Çikaqoya yol tapmalıdırlar. Lakin, bu elə də asan deyildir. Çünki, onları polis, yerli banda və millətçi qrup təqib edir. Üstəlik də, artıq hava qaralır, onlar qara eynək taxır, Çikaqoya qədər isə 106 mil məsafə var.

Onların İlahi missiyası olduğunu nəzərə alaraq onlara ən təhlükəsiz yol tapmaqda kömək edin. Ən təhlükəsiz yol, tutulmamaq ehtimalı ən böyük olan yoldur.

Giriş verilənləri

Birinci sətirdə iki ədəd yazılır: n (2n100) və m (1mn · (n - 1) / 2), n - yolayırıcılarının sayı, m - küçələrin sayı.

Sonrakı m sətrin hər birində üç ədəd: a, bp (1a, bn, ab, 1p100) yazılır. Burada ab - küçələrin ücları, p isə Blyuz qardaşlarının həmin küçədən gizli keçmə ehtimalıdır (faizlə). Bütün küçələr ikitərəflidir və istənilən iki yolayırıcı arasında küçə sayı birdən çox deyil.

Çıxış verilənləri

1 (Palas Otel)–dən n–ci yolayırıcına qədər ən təhlükəsiz yolun ələ keçməmə ehtimalını hesablayın və elə hesab edin ki, bu cür yol mövcuddur.

Axtarılan ehtimalı vergüldən sonra 6 rəqəm dəqiqliyi ilə faizlə çıxarın. Cavabı aşağıda göstərilən formatda çıxarmaq lazımdır.

Göstəriş

Ən təhlükəsiz yol: 1435 olar.

prb1109.gif

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
Çıxış verilənləri #1
61.200000 percent
Mənbə Летняя Школа 2010, Севастополь, день М.Медведева