Programozás‎ > ‎Feladatok‎ > ‎

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 <= D <= 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 <= R <= 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 <= N <= 50), a járat útvonalát leíró pontok száma (ahol kanyarodik)
    • f a jegyár az adott járaton (0 <= f <= 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

Bemenet  Kimenet
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

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

Címkék

A feladat forrása: ACM???
Algoritmusok: 

megoldás