NézetNyomtat

Buszok (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok

Buszok

Egy városban az úthálózat csupa észak-dél és kelet-nyugat irányú útból áll. A helyi tömegközlekedés R buszjáratból áll. A járatok rögzített útvonalon közlekednek, minden kereszteződésben van megálló. (A kereszteződés az, ahol az egymásra merőleges utak metszik egymást.) Minden útvonalon pontosan egy busz jár, mindegyik járaton külön ára van a buszjegynek, de egy járaton bármennyit lehet utazni a jeggyel. Átszálláskor viszont új jegyet kell venni.
Néha persze gyalogolni is kell, hiszen nem mindegyik kereszteződésen halad át buszjárat útvonala. A séta is ugyanazokon az utcákon történhet, ahol a buszok járnak, nincsenek érdekes rövidítések.
Egy turista A-ból B-be szeretne eljutni, de mivel nyaral, legfeljebb D távolságot szeretne gyalogolni. (Két szomszédos kereszteződés távolsága az egység.) Ráadásul a lehető legolcsóbban akarja megoldani az utazást.

Feladat

Írj programot, ami megadja a legolcsóbb út árát, vagy kiírja, hogy "LEHETETLEN", ha nincs megoldása a feladatnak.

Bemenet

  • az első sor $D$ értékét adja meg $(0 \leq D \leq 300)$
  • a második sor $A$ koordinátáit
  • a harmadik $B$ koordinátáit írja le
  • a koordináták 1 és 100,000,000 közé esnek
  • $A$ és $B$ különböző
  • a negyedik sor $R$ értékét adja meg $(1 \leq R \leq 100)$, tehát a buszjáratok számát
  • a következő $R$ sor egy-egy buszjáratot ír le a következő számokkal:
    • $N$ $(4 \leq N \leq 50)$, a járat útvonalát leíró pontok száma (ahol kanyarodik)
    • $f$ a jegyár az adott járaton $(0 \leq f \leq 1,000,000)$
    • majd $N$ számpár, a kanyarok koordinátái
    • a kanyarok között egyenesen halad a busz, a kanyarok 90°-osak

Kimenet

A kimenet egyetlen sora a legolcsóbb utazás árát, vagy a "LEHETETLEN" szót tartalmazza.

Példák és egyben tesztadatok

BUSZ.BEBUSZ.KI
4
3 7
13 1
2
6 2 14 8 5 8 5 6 11 6 11 3 14 3
4 5 16 4 7 4 7 2 16 2
2
BUSZ.BEBUSZ.KI
2
1 5
10 7
3
4 10 1 4 5 4 5 6 1 6
4 10 5 5 5 7 7 7 7 5
4 20 9 5 9 1 7 1 7 5
LEHETETLEN