„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés
Ewsd (vitalap | szerkesztései) |
|||
| 67. sor: | 67. sor: | ||
===4. Feladat=== | ===4. Feladat=== | ||
Éllistával adott n csúcsú, élsúlyzott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a követekző k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk. | |||
Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk! | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||