1109. Ç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 (2 ≤ n ≤ 100) və m (1 ≤ m ≤ n·(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, b və p (1 ≤ a, b ≤ n, a≠b, 1 ≤ p ≤ 100) yazılır. Burada a və b küçələrin sonluqları, 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.

Giriş verilənlərinə nümunə

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ərinə nümunə

61.200000 percent

Göstəriş

Ən təhlükəsiz yol: 1 → 4 → 3 → 5 olar.

HƏLLİ

qraflar – Dijkstra alqoritmi

Alqoritmin analizi

Məsələ klassik Dijkstra alqoritmi ilə həll edilir. Lakin qısaltma əməliyyatında yolların uzunluqlarının cəmi deyil, ələ keçirilməmə ehtimalların hasili istifadə edilir. d[i] qiyməti i təpəsinə qədər olan ən qısa yola deyil, başlanğıc təpədən i təpəsinə gedən yolda ələ keçirilməmə ən böyük ehtimala uyğundur.

Alqoritmin reallaşdırılması

Dijkstra alqoritmində istifadə edilən massivləri elan edək. Məsafələr matrisi mas massivində saxlanılır.

int used[MAX];

double mas[MAX][MAX], d[MAX];

Giriş verilənlərini oxuyuruq. Ehtimalların qiymətlərini elə bölürük ki, onların qiymətləri 0-dan 1-ə qədər intervalda yerləşsin.

scanf("%d %d",&n,&m);

memset(mas,0,sizeof(mas));

while(m--)

{

scanf("%d %d %d",&i,&j,&per);

mas[i][j] = mas[j][i] = per / 100.0;

}

Dijkstra alqoritmini icra edirik. Mənbə ilk təpədə (Palas Mehmanxanası) yerləşir.

memset(used,0,sizeof(used));

memset(d,0,sizeof(d)); d[1] = 1;

for(i = 1; i < n; i++)

{

max = 0;

for(j = 1; j <= n; j++)

if (!used[j] && d[j] > max) {max = d[j]; w = j;}

for(j = 1; j <= n; j++)

if (!used[j]) d[j] = maximum(d[j],d[w] * mas[w][j]);

used[w] = 1;

}

Qrafın n-ci təpəsinə (Çikaqoda J. Deyli mehmanxanası) aparan təhlükəsiz yolun seçilməsini faizlə veririk.

printf("%.6lf percent\n",d[n]*100);