Egy megye településeiről tudjuk, hogy bármely településről bármelyik másikra pontosan egy útvonalon lehet eljutni. Egy üzlethálózat minél több településen szeretne üzletet nyitni. Tudjuk, hogy melyik településen van a raktár, ahonnan az egyes üzletekbe szállítaná az árut. Ismerjük, hogy melyik településen mekkora hasznot fog hozni az üzlet, valamint hogy melyik út használatáért mekkora úthasználati díjat kell fizetni. Az összhaszon az üzletekben termelt haszonból levonva az úthasználati díjakat.
Feladat
Írjunk programot, ami kiszámítja, hogy mekkora az elérhető legnagyobb haszon és ehhez mely településeken kell üzletet nyitni!
Bemenet
A bemenet első sorában a települések N száma (1 <= N <= 10000) és a raktáros település R sorszáma (1 <= R <= N) van. A második sor pontosan N egész számot tartalmaz (egy-egy szóközzel elválasztva), az i-edik szám az i. településem elérhető hasznot. A következő N-1 sorban három egész szám van (egy-egy szóközzel elválasztva): két település sorszám, amelyek között kétirányú út van, és az érte fizetendő úthasználati díj.
Kimenet
Az első sorbába azt az elérhető legnagyobb hasznot kell írni! A második sorba a megnyitandó üzletek M számát kell írni, a harmadikba M sorszámot, egy-egy szóközzel elválasztva: azon települések sorszámát, ahol üzletet nyitunk! A számok sorrendje közömbös. Több megoldás esetén bármelyik megadható.
Példa
Bemenet |
Kimenet |
10 2 100 100 50 50 50 100 200 100 50 50 1 2 200 3 4 10 4 5 10 4 2 100 2 6 10 6 7 100 6 8 150 8 9 30 10 8 60 | 320 6 2 3 4 5 6 7
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2012 3. forduló, 11-13. évfolyam
Algoritmusok:
megoldás |