== include(page="template/taskheader" task_id="posta2") ==
Într-o ţară minunată, cele $N$ oraşe sunt legate între ele prin $N-1$ şosele astfel încât din fiecare oraş se poate ajunge în oricare alt oraş. Se ştie costul benzinei necesare pentru parcurgerea fiecărei şosele şi costul de intrare în fiecare oraş. Ţirbi, managerul poştei, trebuie să aleagă sediul poştei, ştiind că va avea de livrat colete în $M$ oraşe precizate, plecând de la sediul poştei şi revenind după livrarea coletelor tot la sediul poştei. El trebuie să aleagă sediul astfel încât să minimizeze costul transporturilor, ţinând cont că poşta va întocmi un contract cu guvernul prin care va fi scutită de:
* toate taxele de intrare din oraşul în care îşi stabileşte sediul;
* prima intrare în oricare alt oraş, iar pentru restul intrărilor se plăteşte taxa.
h2. Cerinţă
Cunoscând numărul de oraşe, şoselele, taxele de intrare în fiecare oraş şi cele $M$ oraşe în care se livrează coletele, ajutaţi-l pe Ţirbi să calculeze costul minim necesar pentru livrarea comenzilor.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $posta2.in$ conţine pe prima linie două numere naturale $N$ şi $M$ separate printr-un spaţiu, cu semnificaţia din enunţ. Pe următoarele $N-1$ linii se vor afla câte trei numere $x$, $y$, $z$, separate prin câte un spaţiu, cu semnificaţia că există şosea de la oraşul $x$ la oraşul $y$ având costul $z$. Pe următoarea linie se află $N$ numere naturale reprezentând taxa de intrare din fiecare oraş. Ultima linie conţine $M$ numere naturale reprezentând oraşele în care poşta trebuie să livreze comenzi.
Fişierul de intrare $posta2.in$ ...
h2. Date de ieşire
În fişierul de ieşire $posta2.out$ conţine costul minim al unui transport.
În fişierul de ieşire $posta2.out$ ...
h2. Restricţii
* $2 ≤ M ≤ N ≤ 100.000$
* Toate taxele şi costurile sunt numere naturale strict pozitive mai mici sau egale cu $100.000$.
* Maşina poate trece prin oricare oraş sau pe orice şosea de oricâte ori.
* Oraşele în care livrează comenzi sunt distincte.
* Pentru $10%$ din teste $M ≤ 3$
* Pentru $30%$ din teste $N ≤ 1.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. posta2.in |_. posta2.out |
| 7 3
1 2 3
2 3 5
2 4 2
4 7 4
1 5 7
5 6 1
2 1 1 2 1 2 1
1 4 6
| 28
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Se va alege sediul în oraşul $1$ şi se va parcurge următorul traseu:
$1 → 2 → 4 → 2 → 1 → 5 → 6 → 5 → 1$
Costul benzinei este $26$
Costul taxelor este $2$ (oraşul $2 +$ oraşul $5$)
În oraşele $4$ şi $6$ nu se plăteşte taxă deoarece se intră o singură dată.
...
== include(page="template/taskfooter" task_id="posta2") ==
