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

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


Timp maxim de executie/test:
1.2 secunde
Memorie totala disponibila/stiva:
64 MB/32 MB

Zapada a luat din nou prin surprindere primaria. Primarul a chemat de urgenta serviciul deszapeziri si a dat o lista cu strazile din oras care trebuie sa fie obligatoriu curatate. Primarul a selectat strazile din lista astfel incat numarul lor sa fie cat mai mic posibil, dar totusi intre oricare doua intersectii din oras sa existe legatura.
La serviciul deszapeziri lucreaza doi angajati, Vasilica si Ionica, pe doua utilaje. In acest moment si angajatii si utilajele se gasesc la sediul serviciului deszapezri, situat in una dintre intersectiile din oras. Un utilaj de deszapezire consuma 1 litru de benzina/1 metru (indiferent daca se deplaseaza pe o strada inzapezita sau deszapezita).
Vasilica si Ionica trebuie sa deszapezeasca toate strazile din lista data de primar, astfel incat cantitatea totala de benzina consumata sa fie minima.
Cand toate strazile din lista data de primar sunt curatate, utilajele pot fi parcate in ultima intersectie vizitata. Evident Ionica si Vasilica nu trebuie sa-si parcheze utilajele neaparat in aceeasi intersectie.

Cerinta

Scrieti un program care sa determine conatitatea minima de benzina necesara pentru curatarea tuturor strazilor din lista data de primar.

Date de intrare

Fisierul de intrare zapezi.in contine:
- pe prima linie doua numere naturale N si S, unde N este numarul de intersectii din oras, iar S este numarul de ordine al intersectiei in care se afla sediul serviciului deszapeziri, cea din care pleaca initial Vasilica si Ionica (intersectiile sunt numerotate de la 1 la N).
- fiecare dintre urmatoarele N-1 linii contine 3 numere naturale A B C cu semnificatia "intersectiile A si B sunt conectate direct printr-o strada de lungime C metri".

Date de iesire

Fisierul de iesire zapezi.out contine pe prima linie cantitatea minima de benzina necesara pentru curatarea tuturor strazilor din lista data de primar.

Restrictii

  • 1 <= N <= 2000
  • 1 <= S, A, B <= N
  • 1 <= C <= 100

Exemple

zapezi.in zapezi.out
5 2
1 2 1
2 3 2
3 4 2
4 5 1
6

 

zapezi.in zapezi.out
5 1
1 2 1
2 3 1
3 5 1
3 4 1
5

 

zapezi.in zapezi.out
4 1
1 3 2
1 2 3
1 4 4
11

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Software recomandat
surse trimise | ajutor