Karaván
A feladat szövege
Egy sivatagban N város található, melyek között az év egy időszakában naponta indulnak karavánok. Ezen időszakon kívül azonban egyetlen sem indul.
Feladat:
Készíts programot, amely meghatározza két adott, A B városra és H határidőre a következőket:
- Legkorábban mikorra érhetünk az A városból a B városba;
- Legalább hány nap kell ahhoz, hogy az A városból a B városba érjünk, ha nincs megkötés sem az indulási, sem az érkezési időre;
- Legkésőbb melyik napon kell elindulni az A városból, hogy legkésőbb a megadott H határidőig a B városba érjünk.
Bemenet:
A KARAVAN.BE állomány első sorában a városok száma (1<=N<=100) és a karavánkapcsolatok száma (1<=M<=5000) van. A következő M sor mindegyikében két város-sorszám (X,Y) és két napsorszám (P,Q) van egy-egy szóközzel elválasztva, ami azt jelenti, hogy az X. városból az Y városba az év P. és Q. napja között (P-t és Q-t is beleértve) indulnak karavánok. Az állomány utolsó sorában az indulási (A) és az érkezési (B) hely sorszáma van, valamint annak a napnak az éven belüli H sorszáma, amikor legkésőbb meg kell érkezni a B. városba, egy-egy szóközzel elválasztva. A karavánok mindig reggel indulnak és még aznap este megérkeznek a célállomásra.
Kimenet:
A KARAVAN.KI állományba három sort kell írni. Minden sorban egyetlen szám szerepeljen: a részfeladat megoldásának értéke. Ha egy részfeladatnak nem létezik megoldása, akkor a -1 számot kell kiírni.
Példa
| KARAVAN.BE | KARAVAN.KI |
| 5 7
1 2 2 7
1 5 2 4
2 3 1 2
2 5 8 9
3 4 6 7
5 4 3 9
4 2 1 2
1 4 10 | 3
2
7 |
Tesztadatok
