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

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


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Ion s-a îndragostit de Maria si doreste sa o viziteze cât mai des posibil. Ion locuieste în orasul Iasi, iar Maria locuieste în Lugoj. Ion calatoreste întotdeauna cu masina sa, care consuma 1dl de benzina /km. Rezervorul masinii are o capacitate de K dl. De la Iasi la Lugoj sunt M drumuri diferite si câteva puncte de intersectie notate 1,2,…,N. Iasi, orasul de plecare a fost notat cu 1, iar Lugoj, orasul de sosire a fost notat cu N. În fiecare dintre cele N puncte de intersectie sunt statii de benzina, dar pretul benzinei poate sa difere de la o statie la alta.

Cerinta

Scrieti un program care sa determine cel mai scurt drum de la Iasi la Lugoj si o strategie de a cheltui pe acest drum cât mai putini bani pe benzina.

Date de intrare

Fisierul de intrare se numeste lover.in. Prima linie a fisierului de intrare contine 3 numere naturale N M K. În fiecare dintre urmatoarele M linii se gasesc 3 numere naturale X Y D, reprezentând distanta D exprimata în km de la punctul de intersectie X la punctul de intersectie Y. Fiecare dintre urmatoarele N-1 linii contine un numar natural Pi reprezentand pretul benzinei in statia i.

Date de iesire

Fisierul de iesire lover.out are o singura linie pe care afisati, separate prin spatiu, doua numere lg sum (lungimea celui mai scurt drum de la Iasi la Lugoj si suma minima cheltuita pe benzina).

Restrictii

  • N <= 3000 este un numar natural care reprezinta numarul de puncte de intersectie.
  • Pi <= 1000 (1 <= i <= N-1) sunt numere naturale, Pi reprezinta pretul pentru 1 dl de benzina la statia i.
  • M <= 11000 este un numar natural care reprezinta numarul de drumuri existente între cele N puncte de intersectie.
  • K <= 300 este un numar natural care reprezinta capacitatea rezervorului masinii, exprimata în dl.
  • La fiecare statie de benzina exista o cantitate suficient de mare de benzina.
  • Doua puncte de intersectie pot fi conectate printr-un singur drum.
  • În datele de test exista un singur drum minim.

Exemplu

lover.in lover.out
4 5 6
1 2 5
1 3 4
3 2 2
2 4 2
3 4 5
5
10
8
7 40

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, zapezi, 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, 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, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, 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 Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
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, zapezi, litoral, 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
Despre drum minim: miniasm, robot, furtuna, excursie, arthur, bete, zmeu, trafic, masina1, bomboane, traseu, litoral, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
Software recomandat
surse trimise | ajutor