Gazdaságos tankolás
(Megoldás)
Versenyek > ACM
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok
Versenyek > ACM
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok
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
Írj 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 \le n \le 1000$)és
a köztük haladó utak számát ($0\le m \le 10000$) adja meg.
Ezután a második sorban $n$ egész következik, a benzinár a városokban.
($ 1 \le p_i \le 100$, ahol $p_i$ a benzin ára az
$i.$ városban).
A következő $m$ sor mindegyikében három egész található,
$0 \le u, v \lt n$ és $1 \le d \le 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 \le q \le 100$, a kérdések száma, és ezt követi $q$ sor, mindegyikben három egész
$ 1 \le c \le 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
| tank.be | tank.ki |
| 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 |