A megoldás
A
Zombik című feladatban használt legrövidebbút kereső algoritmust átalakításást fogjuk itt is használni. De előbb találjuk ki, hogy hogyan tároljuk el a térképet:
Tárolás a memóriában
Az egy városhoz kapcsolódó, és a két város közötti karavánkapcsolatokra nincsen semmilyen korlát, csak annyit tudunk, hogy az összes kapcsolatok száma legfeljebb 5000. Ezért felveszünk néhány 5000-es tömböt nekik. A városokat és a kapcsolatokat is 1-től sorszámozzuk. A tömbök: az i-edik karavánkapcsolat a v1[i] sorszámú városból a v2[i]-edik városba visz, és az év n1[i]-edik napjától az n2[i]-edik napjáig közlekedik.
Az első részfeladat
Írjuk fel minden városhoz, hogy mennyi idő alatt érhetőek el. Pontosabban azt, hogy melyik nap reggelére érhetőek el. Kezdetben ez minden városhoz végtelen, kivéve A-t, amihez 1. A végtelen azt jelenti, hogy a város nem érhető el, vagy legalábbis azt, hogy még nem tudjuk, hogy elérhető-e. Jelölhetjük pl. -1-el, vagy egy olyan nagy számmal, ami biztosan nem fordulhat elő. (Ezt a nagy számot mindenképpen rögzítsük konstansként, és a legjobb az, ha a számábrázolás felső határának állítjuk be.) A továbbiakban a "-1-es" megoldást fogjuk megnézni.
Az algoritmus a következő, már jól ismert lépés ismételgetéséből fog állni: vegyük sorra a városokat, és ha olyat találunk, aminek nem végtelen már az elérési ideje, akkor nézzük meg, hogy a karaván-kapcsolatain keresztül el lehet-e jutni belőle más városokba. Ha valamelyik ilyen városba hamarabb el lehet így jutni, mint a feljegyzett ideje, akkor ezt a hamarabbi napot jegyezzük fel neki elérési időnek. Az elérési idők számolásánál figyelni kell arra, hogy két város között csak bizonyos időszakokban van út. Ilyenkor természetesen a lehető legkorábbi időpontban ki kell használni az utat. És az előző órákhoz hasonlóan, ez az algoritmus itt is akkor fog megállni, ha már lefutott egy olyan lépés, amiben nem volt elérési idő csökkentés.
A következő függvény megmondja, hogy ha t napon reggel indulunk az A városból, akkor legkorábban melyik nap estére érkezhetünk meg B-be. Felhasználja még az ido[] tömböt is, aminek kezdetben minden eleme -1, és később az i-edik eleme az i-edik város elérési ideje lesz. (Tehát az, hogy melyik nap reggel lehet belőle továbbindulni.) Annyit érdemes még módosítani az algoritmuson, hogy nem a városokat veszi sorra egy lépésben, hanem a karaván-kapcsolatokat. Ez a két dolog valójában ekvivalens, de a másodikat könnyebb gyors(abb)ra megírni.
Eljárás Leghamarabb(t)
ido[a]:= t;
kesz := Hamis;
Ciklus Amíg (kesz = Hamis)
kesz := Igaz;
Ciklus i := 1-től M-ig
Ha Csokkent(i) Akkor
kesz := Hamis;
Elágazás Vége
Ciklus Vége
Ciklus Vége
Ha ido[b] = -1 Akkor Leghamarabb:= -1
Különben Leghamarabb := ido[b] - 1;
Eljárás Vége
A kesz fogja jelezni, ha nem volt csökkentés egy körben. A Csokkent(k) pedig megnézi, hogy csökken-e a v2[k] város elérési ideje, ha v1[k] városból a k karavánnal megyünk oda. (Természetesen úgy, hogy ha v1[k]-ból legkorábban csak ido[ v1[k] ] napon indulhatunk el.) Ha igen, akkor csökkenti, és Igazzal tér vissza, ha nem, akkor nem csinál semmit, és Hamissal tér vissza. A Csokkent eljárás:
Eljárás Csokkent(k)
start := v1[k];
cel := v2[k];
Ha (ido[start] > n2[k]) vagy (ido[start] = -1) Akkor
Csokkent := Hamis;
Különben
Ha (ido[start] <= n1[k]) Akkor
startnap := n1[k];
Különben
startnap := ido[start];
Elágazás Vége
Ha (startnap + 1 < ido[cel]) vagy (ido[cel] = -1) Akkor
ido[cel] := startnap + 1;
Csokkent := Igaz;
Különben
Csokkent := Hamis;
Elágazás Vége
Elágazás Vége
Eljárás Vége
Ha ido[v] > n2[k] akkor túl későn érkeztünk a v városba, és lekéstük a karavánt. Ha elértük, akkor megnézzük, hogy a karaván kezdőnapja előtt, vagy után érkeztünk, és ez alapján meghatározzuk a lehetséges legkorábbi
indulás időpontját, startnap-ot. Így az első részfeladat megoldása:
Kiir( Leghamarabb(1) );
...ha nem felejtkezünk el az ido[] tömb inicializációjáról.
A másik két részfeladat
Ezeket a részfeladatokat az előző rész megoldásának Leghamarabb(t) a felhasználásával lehet könnyen megcsinálni. Meg kell keresni a legkésőbb befejeződő karaván utolsó napját: legyen pl. utso-ban. Majd nézzük végig a napokat 1-től utso-ig, és nézzük meg, hogy egy adott napon indulva A-ból, mikorra érkezhetünk B-be. Ezek közül kell kiválasztani a legrövidebb utazási időtartamú utazást, és a legkésőbb kezdődő, de H határidőre megérkező utazást.
leg_rovidebb := -1;
leg_kesobb := -1;
Ciklus i := 1-től usto-ig
erk := Leghamarabb(i);
Ha erk <= H Akkor
Ha (i > leg_kesobb) Akkor
leg_kesobb := i;
Elágazás vége
Elágazás vége
Ha (erk - i + 1 < leg_rovidebb) vagy (leg_rovidebb = -1) Akkor
leg_rovidebb := erk - i + 1;
Elágazás Vége
Ciklus vége
Kiir(leg_rovidebb);
Kiir(leg_kesobb);
Megoldások
