Komentarz do zadania 3 z egzaminu z ASD 26 stycznia 2010
========================================================

Zadanie okazało się bardzo proste. Właściwie istniały dwa
sensowne rozwiązania tego zadania, oba działające w takim
czasie, jak algorytm Dijkstry dla wejściowego grafu,
czyli O(nlogn + m) w przypadku kopców Fibonacciego i
O((m+n)logn) w przypadku kopców zupełnych.

Pierwsze rozwiązanie: robimy Dijkstrę z s, ale wagą
nie są normalne wagi, lecz pary (waga, liczba krawędzi),
porównywane leksykograficznie. Czyli krawędź o wadze w
ma teraz wagę (w, 1).
Rozwiązanie to można było też implementować nie mówiąc
o tym, że to są pary, tylko po prostu trzymać najmniejszą
liczbę krawędzi na najkrótszej ścieżce w tablicy l
i w funkcji Relax aktualizować v jeśli:
d(v) > d(u) + w(u,v) lub (d(v) = d(u) + w(u,v) i l[v] > l[u] + 1).
W kolejce priorytetowej wystarczy wówczas sortować tylko po d,
nie trzeba patrzeć na l - korzystamy tu z tego, że wagi są
dodatnie.

Drugie rozwiązanie: robimy najnormalniejszą Dijkstrę z s,
a następnie puszczamy z s BFSa ale takiego, co może chodzić
tylko krawędziami takimi, że jeśli chce pójśc z u do v,
to musi być d(u) + w(u,v) = d(v).

Najczęstszym błędem był brak oszacowania złożoności algorytmu.
Parę osób niepoprawnie zmodyfikowało funkcję Relax w rozwiązaniu
pierwszym.

Punktacja:
8 pkt   wzorcowe rozwiązanie
7 pkt   wzorcowe rozwiązanie, ale ze złym oszacowaniem złożoności
        lub jej brakiem
3-5 pkt rozwiązanie niby wzorcowe, ale coś pomieszane w funkcji Relax
0 pkt   rozwiązanie niepoprawne