Ładny brzuch
Oto zadanie
Myslalem dugo nad tym zadankiem, w kocu po wielu godzinach cus wykodziem. Byem zadowolony e wreszcie by moe rozwizaem do trudne zadanie. Wrzucam rozw. na maina i.... 9 pkt :/ Okazuje sie ze moj algorytm sie w pewnych przypadkach wykrzacza. Ale do rzeczy. Moj algo wyglada mniej wiecej tak (jesli chodzi o szukanie sciezki):
Jest to poprostu zwyczajny algorytm Dijsktry z dooon dodatkow instrukcj warunkowa, ktora pilnuje, zeby algo nie zadzialal gdy kat jest zbyt duzy. Niby wszystko OK, ale na prawde tak nie jest. Mianowicie wykrzaczenie nastapi w momencie, gdy najkrotsza droga do poprzednika wierzcholka do ktorego chce dojsc jest taka, ze do momentu tego poprzednika mozna ni isc (kty s dobre), ale juz do docelowego wierzcholka nie. Trzeba by wtedy isc inna droga, ale dijskra juz jej nie wyszuka, gdy ta droga jest juz odrzucona jako zbyt dluga. I teraz co tu zrobic? Da sie wogole przerobic algo Dijsktry zeby dzialal tu jak trzeba, czy przez to ze jest zachlanny takiej mozliwosci nie ma i trza z czegos innego skorzystac?
Oto moj kod
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Myslalem dugo nad tym zadankiem, w kocu po wielu godzinach cus wykodziem. Byem zadowolony e wreszcie by moe rozwizaem do trudne zadanie. Wrzucam rozw. na maina i.... 9 pkt :/ Okazuje sie ze moj algorytm sie w pewnych przypadkach wykrzacza. Ale do rzeczy. Moj algo wyglada mniej wiecej tak (jesli chodzi o szukanie sciezki):
Jest to poprostu zwyczajny algorytm Dijsktry z dooon dodatkow instrukcj warunkowa, ktora pilnuje, zeby algo nie zadzialal gdy kat jest zbyt duzy. Niby wszystko OK, ale na prawde tak nie jest. Mianowicie wykrzaczenie nastapi w momencie, gdy najkrotsza droga do poprzednika wierzcholka do ktorego chce dojsc jest taka, ze do momentu tego poprzednika mozna ni isc (kty s dobre), ale juz do docelowego wierzcholka nie. Trzeba by wtedy isc inna droga, ale dijskra juz jej nie wyszuka, gdy ta droga jest juz odrzucona jako zbyt dluga. I teraz co tu zrobic? Da sie wogole przerobic algo Dijsktry zeby dzialal tu jak trzeba, czy przez to ze jest zachlanny takiej mozliwosci nie ma i trza z czegos innego skorzystac?
Oto moj kod