.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » posta

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
posta


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
32MB / 1MB

Î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.

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.

Date de intrare

Fişierul de intrare posta.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.

Date de ieşire

Fişierul de ieşire posta.out conţine costul minim al unui transport.

Restricţii

• 2 ≤ M ≤ N ≤ 100000
• Toate taxele şi costurile sunt numere naturale strict pozitive mai mici sau egale cu 100000.
• Maşina poate trece prin oricare oraş sau pe orice şosea de oricâte ori.
• Oraşele în care livrează comenzi sunt distincte.

Exemple

posta.inposta.outExplicaţii
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 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ă.

autor: Cosmin Tutunaru
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor