Feladat
Adott egy bevásárlólista, ami olyan termékeket sorol fel, amiket meg akarunk vásárolni. Adott továbbá néhány bolt pozicióinak a listája síkbeli euklideszi koordinátákkal megadva. Azt is tudjuk, hogy az egyes boltok mely termékeket mennyi pénzért árulnak. Adott az üzemanyag ára is. Kérdés az, hogy legkevesebb mennyi pénz szűkséges az összes a listán szereplő termék megvásárlásához és hazaszállításához. A kiindulási és befejezési pont is a (0,0) koordinátájú pozíció kell legyen.
Az érdekesség kedvéért romlandó (perishable) termékek is vannak a listánkon. Valahányszor, ha egy boltban vásárolt termékek között romlandók is vannak, akkor a bolt elhagyása után vissza kell térnünk haza, a (0,0) pozicióra. Minden a bevásárlólistán szereplő termék megvásárolható legalább egy boltban, tehát a bevásárlókörút mindig sikeres lesz.
Bemenet
A bemenet első sora megadja a tesztesetek számát, N-et. Ezután N teszteset következik. Minden eset a következő sorral kezdődik:
num_items num_stores price_of_gas
Ez három egész szám: num_items a bevásárlólistán lévő termékek száma; num_stores a boltok száma; price_of_gas az egységnyi távolság megtételéhez szűkséges üzemanyag ára.
A következő sor a bevásárlólistán lévő num_items darab termék neveit sorolja fel. Ezek szóközökkel vannak elválasztva és csak kisbetűket tartalmaznak. Ha egy termék romlandó, akkor a nevét egy felkiáltójel követi közvetlenül. Egy termék legfeljebb egyszer szerepelhet a listában. A következő num_stores darab sor formája a következő lesz:
x_pos y_pos item1:price1 item2:price2 ...
Mindegyik sor egy bolt pozicióját, és az ott vásárolható termékek árait tartalmazza. Csak olyan termékek lesznek ezekben a listákban, amik a bevásárlólistánkon is szerepeltek. A romlandó termékek neve után itt már nincs felkiáltójel. Egy bolt listáján egy termék nem fog többször szerepelni. Nem lesz két bolt azonos pozición, és nem lesz bolt a (0,0) pozición sem.
Kimenet
Minden tesztesethez egy sorot kell kiírni, melynek formája a következő:
Case #x: 0.0000000
Az eredmény a legkisebb lehetséges költség, 7 tizedesjegyre kerekítve.
A bemenet korlátai
1 $\leq$ N $\leq$ 100,
0 $\leq$ price_of_gas $\leq$ 1000,
-1000 $\leq$ x_pos $\leq$ 1000,
-1000 $\leq$ y_pos $\leq$ 1000,
1 $\leq$ price of each item $\leq$ 1000.
Kis tesztadatok
Futási időlimit: ~3 perc
1 $\leq$ num_items $\leq$ 5,
1 $\leq$ num_stores $\leq$ 10.
Nagy tesztadatok
Futási időlimit: ~7 perc
1 $\leq$ num_items $\leq$ 15,
1 $\leq$ num_stores $\leq$ 50.
Példa
| Input |
Output |
| 2
1 2 10
cookies
0 2 cookies:400
4 0 cookies:320
3 3 5
cookies milk! cereal
0 2 cookies:360 cereal:110
4 0 cereal:90 milk:150
-3 -3 milk:200 cookies:200 |
Case #1: 400.0000000
Case #2: 519.2920690 |
Tesztadatok
