Vidámpark
(Megoldás)
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2007 > Döntő > 11-13. osztály
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2007 > Döntő > 11-13. osztály
Vidámpark
Egy vidámpark $N$ részlegből áll, a részlegeket az $1,\ldots,N$ számokkal azonosítják, az 1. részleg a bejárat, az N. részleg a kijárat. Minden részlegbe ugyanazzal az egységes jeggyel lehet bemenni. A részlegeket egyirányú utak kötik össze. Ha egy részlegben elhasználunk egy jegyet, akkor el kell hagyni azt a részleget, tehát át kell menni egy másik részlegbe. Ha K darab jegyünk van, és mindet el akarjuk használni, akkor meg kell határoznunk egy olyan $R_1=1, \ldots, R_k=N$ sétát, amely a részlegeknek egy olyan felsorolása, amely a bejárattal kezdődik, a kijárattal végződik, és minden $i$-re ($1\le i < K$) az $R_i$ részlegből közvetlenül át lehet menni az $R_{i+1}$ részlegbe. (Ugyanazon részleg természetesen többször is előfordulhat a sétában.)
Feladat
Készíts programot (VIDAM.PAS, VIDAM.C, …), amely meghatároz egy olyan pontosan $K$ részleget tartalmazó sétát, amely a bejárattal kezdődik, a kijárattal végződik!
Bemenet
A VIDAM.BE szöveges állomány első sora három egész számot tartalmaz egy-egy szóközzel elválasztva. Az első a részlegek száma ($2\le N \le 100$), a második a részlegeket összekötő közvetlen utak száma ($1 \le M\le 5000$), a harmadik pedig a jegyek száma ($2\le K \le 200$). A további $M$ sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva ($1\le U,V\le N, U\ne V$), ami azt jelenti, hogy az $U$ részlegből van közvetlen út a $V$ részlegbe.
Kimenet
A VIDAM.KI szöveges állomány egyetlen sort tartalmazzon! A sor az egyetlen 0 számot tartalmazza, ha nincs megoldás! Egyébként pontosan $K$ egész számot egy-egy szóközzel elválasztva, ami egy $K$ hosszúságú séta a bejárattól a kijáratig!
Példa
| VIDAM.BE | VIDAM.KI |
|
6 10 7 1 2 2 1 2 6 1 5 1 3 3 5 5 4 5 6 4 3 6 4 |
1 5 6 4 3 5 6 |