datapub.zip
Riešenie na 10/10
spraviť kondenzovaný graf Tarjanom
source nodes sú korene kondenzovaného grafu
z kondenzovaného grafu vytvoriť nový takto:
min_reverse - každú pôvodnú hranu pridať s váhou 0, každú obrátenú hranu pridať s váhou 1
Dijkstrom hľadať najlacnejšie cesty z komponenty, v ktorej sa nachádza central node, do všetkých ostatných komponent, nakoniec len sčítať ceny najlacnejších ciest do source nodov
Nahoru