NézetNyomtat

Gazdaságos tankolás (Megoldás)
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.betank.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

Tesztadatok