Raktár
Olimpiai válogató feladat alapján
Egy vállalat több városban gyárt alkatrészeket. Minden városban egy raktárban tárolja a legyártottakat. A termelést egy központi raktárban akarják összesíteni. Bizonyos várospárokat közvetlen kétirányú út köt össze. Bármely két város között pontosan egy út van. U városból V városba D darab alkatrész szállításának a költsége t(U,V)*D, ahol t(U,V) U és V távolságát jelöli, amely az U-t és V-t összekötő út hossza. A központi raktár helyét úgy kívánják meghatározni, hogy a szállítások összköltsége a minimális legyen.
Feladat
A feladat olyan program írása, amely kiszámítja a raktár ideális helyét és a minimális szállítási összköltséget.
Bemenet:
A raktarX.be szöveges állomány első sorában a városok N (1<N<=3000) száma van. A második sor N darab pozitív egész számot tartalmaz, az i-edik szám az i-edik városban gyártott alkatrészek száma, ami nem nagyobb, mint 100. A következő N-1 sor mindegyike két számot tartalmaz, két olyan város sorszámát, melyek között kétirányú út található. A városokat az 1,2,...,N számokkal azonosítjuk.
Kimenet:
A raktarX.ki szöveges állomány első sorába a legkisebb szállítási összköltséget kell írni. A második sorba annak a városnak a sorszámát kell írni, ahol a központi raktárt létesíteni kell. Ha több ilyen lenne, akkor a legkisebb sorszámú várost kell kiírni.
Példa
| raktar0.be | raktar0.ki |
| 8 4 2 1 5 1 2 1 3 5 4 6 7 5 6 5 8 3 8 1 3 3 2 | 31 8 |