Programozás‎ > ‎Feladatok‎ > ‎

Gazdaságos tankolás

Egy európai körutazás során tapasztalható, hogy a benzin ára városról-városra változik. Ha okosan tankolunk, sok pénz megtakarítható.

Feladat

Írjunk programot, ami kiszámítja, hogy két város között hogyan autózhatunk legolcsóbban. Feltesszük, hogy az autó egy egységnyi távon egy egységnyi benzint fogyaszt, és a kiindulópontról üres tankkal indul.

Bemenet

A bemenet első sora a városok számát (1 <= n <= 1000) és a köztük haladó utak számát (0 <= m <= 10000) adja meg. Ezután a második sorban n egész következik, a benzinár a városokban. (1 <= p<= 100, ahol pi a benzin ára az i. városban). A következő m sor mindegyikében három egész található, 0 <= u, v < n és 1 <= d <= 100, ahol u, v két város sorszáma, d pedig a köztük haladó út hossza. Ezután egyetlen szám jön a következő sorban 1 <= q <= 100, a kérdések száma, és ezt követi q sor, mindegyikben három egész 1 <= c <= 100, s és e, ahol c az autó tank-kapacitása, s a kiinduló város sorszáma, e pedig a célváros sorszáma.

Kimenet

Minden kérdéshez írjuk ki az s és e közötti legolcsóbb út árát, vagy az "impossible" szöveget, ha az adott autóval nem lehetséges eljutni s-ből e-be.

Példa

Bemenet  Kimenet
5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4
170
impossible


Tesztadatok

Címkék

A feladat forrása: ACM ???
Algoritmusok: Dijkstra-algoritmus

megoldás