 |
Az S. 160. feladat (2022. március) |
S. 160. Ádám meg szeretné látogatni Évát. A kettejük közt lévő utak hálózata leírható egy irányítatlan gráffal, melyben a csúcsok a kereszteződések és az élek a köztük lévő utak. Ádám az egyes sorszámú kereszteződésből indul és a legnagyobb, \(\displaystyle N\)-es sorszámúba szeretne eljutni.
Ádám eddig mindig a két pont közötti legrövidebb utak valamelyikén ment. Adjuk meg, hányféle különböző legrövidebb út van a két pont között.
Mivel gyakran megy látogatóba, unja már ezeket a lehetőségeket, így most egy olyan útvonalat szeretne választani, amelynek hossza szigorúan nagyobb, mint a legrövidebb út hossza. Adjunk meg, hogy legalább mekkora lesz az új útvonal hossza.
Bemenet: az első sor tartalmazza a kereszteződések \(\displaystyle N\) és az utak \(\displaystyle M\) számát. A következő \(\displaystyle M\) sor mindegyike egy-egy utat ír le a két végpontjával.
Kimenet: az első sorába a legrövidebb utak száma kerüljön. A kimenet második sorába írjuk az új útvonal minimális hosszát. Ha nincs a legrövidebbnél hosszabb út, akkor -1-et kell kiírni.
Minta:
| Bemenet (a / jel sortörést helyettesít) | Kimenet (a / jel sortörést helyettesít) |
| 3 3 / 1 2 / 2 3 / 3 1 | 1 / 2 |
Korlátok: \(\displaystyle 2\le N\le 300\). Időlimit: 1 mp.
Értékelés: a pontok 50%-a kapható arra a megoldásra, amelynél a kimenet első sora helyes.
Beküldendő egy s160.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.
(10 pont)
A beküldési határidő 2022. április 19-én LEJÁRT.
Statisztika:
5 dolgozat érkezett. 10 pontot kapott: Tóth 057 Bálint. 5 pontot kapott: 4 versenyző.
A KöMaL 2022. márciusi informatika feladatai