Az S. 165. feladat (2022. november) |
S. 165. Egy gyorsétteremlánc két különböző étteremben dolgozó alkalmazottja rájött, hogy ha a jelenlegi munkahelyük helyett egymás munkahelyére járnának dolgozni, akkor mindkettőjüknek kevesebbet kellene utazni. Szeretnének javaslatot tenni a felettesüknek a munkahelyek újraosztására, de a probléma sajnos túl bonyolultnak bizonyult, hogy papíron kiszámolják.
Adott egy város úthálózata, mely csúcsokból és az őket összekötő súlyozott élekből áll. Van továbbá valahány éttermünk és D alkalmazottunk, akikről tudjuk, honnan és hova járnak dolgozni. A feladatunk úgy újraosztani a munkahelyeket, hogy az alkalmazottak munkahelytől vett távolságának összege a lehető legkisebb legyen. (Tegyük fel, hogy a dolgozóknak egyéb preferenciája nincs.)
A bemenet első sorában a csúcsok N és az élek M száma található. A következő M sor egy-egy utat ír le, a két végpontjának sorszámával és az él súlyával (az út hosszával). Ezután az alkalmazottak D száma, majd D sorban az alkalmazottak lakhelyének és munkahelyének csúcsszáma található. Mindent 0-tól indexelünk és egy csúcsban legfeljebb egy étterem van.
A kimenet egyetlen sorában az elérhető legkisebb távolságösszeg szerepeljen, ha az újraosztás után minden étteremben ugyanannyian dolgoznak, mint előtte.
Példa:
Megjegyzés: Mint ahogy a példa is mutatja, előfordulhat, hogy valaki így többet fog utazni.
Korlátok: N≤500, M≤1000, D≤100. Időlimit: 1 mp.
Értékelés: A pontok 50%-a kapható, ha a program helyes kimenetet ad a D≤10 esetekre.
Beküldendő egy s165.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.
(10 pont)
A beküldési határidő 2022. december 15-én LEJÁRT.
Statisztika:
2 dolgozat érkezett. 5 pontot kapott: 2 versenyző.
A KöMaL 2022. novemberi informatika feladatai