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

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


Timp maxim de execuţie/test:
0.15 secunde
Memorie totală disponibilă/stivă:
16MB/1 MB

Un turist doreşte să viziteze cele N oraşe de pe malul Dunării. Acestea sunt numerotate cu numere naturale cuprinse între 1 şi N în sensul de curgere. Oraşul 1 (de plecare) se află la izvoare, iar oraşul N la vărsarea în Marea Neagră. Turistul se poate deplasa între oricare două oraşe vecine, la alegere, cu vaporul, microbuzul sau elicopterul. Se cunoaşte costul deplasării între oricare două oraşe vecine cu fiecare dintre cele trei mijloace de transport. De asemenea, dacă într-un anumit oraş se schimbă mijlocul de transport se cunoaşte costul deplasării în oraşul respectiv pentru folosirea altui mijloc de transport.

Cerinţă

Determinaţi costul minim cu care turistul poate vizita toate cele N oraşe de pe valea Dunării ştiind că el pleacă din portul corespunzător oraşului de la izvoare.

Date de intrare

Fişierul de intrare fluviu.in are următoarea structură:
 -   pe prima linie N, numărul de oraşe de pe valea Dunării;
 -   pe linia a doua, N numere naturale reprezentând costul deplasării între port şi autogară, respectiv, pentru fiecare oraş (al i – lea număr reprezintă costul deplasării între portul şi autogara din oraşul i);
 -   pe linia a treia, N numere naturale reprezentând, respectiv, costul deplasării între port şi helioport pentru fiecare oraş de la 1 la N.
 -   pe linia a patra, N numere naturale reprezentând, respectiv, costul deplasării între autogară şi helioport pentru fiecare oraş de la 1 la N.
 -   Pe linia a cincea N-1 numere naturale, al i-lea număr reprezentând costul deplasării cu vaporul între oraşele i şi i+1;
 -   Pe linia a şasea N-1 numere naturale, al i-lea număr reprezentând costul deplasării cu microbuzul între oraşele i şi i+1;
 -   Pe linia a şaptea N-1 numere naturale, al i-lea număr reprezentând costul deplasării cu elicopterul între oraşele i şi i+1.

Date de ieşire

Fişierul fluviu.out va conţine o singură linie pe care va fi scris un număr reprezentând costul minim cu care turistul îşi poate îndeplini dorinţa.

Restricţii

  • 2 <= N <= 50000
  • Costurile de deplasare între orice 2 oraşe consecutive sau între punctele de plecare din acelaşi oraş sunt numere naturale mai mici decât 2 miliarde.
  • Din oraşul i se poate merge direct doar în oraşul i+1 cu oricare dintre mijloacele de transport.
  • Distanţele dintre punctele de plecare ale fiecărui oraş se pot parcurge în ambele sensuri cu acelaşi cost.
  • Rezultatul este un număr natural ce poate fi memorat pe 32 biţi cu semn.

Exemplu

fluviu.in fluviu.out
3
1 1 1
2 2 2
3 3 3
3 3
2 2
1 1
4
prof. Marius Nicoli
Colegiul Naţional „Fraţii Buzeşti” Craiova
mariusnicoli@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: secvente1, raze, bile5, 235, dreptunghiuri, triunghi2, albine1, puteri35, miere, left, arbgraf, reuniune, cazare, atletism, stele, zar1, poteci, avioane, obstacole, liste, acoperire1, minusk, efect, b2k, progresii, reconst, mijloc, romb, alune, patru, galbeni, schi1, restaurare, sort2dist
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
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, 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, 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, lover, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
surse trimise | ajutor