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

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


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

Zmeul le-a inchis pe cele 5 fete ale imparatului in castelul sau. Fat-Frumos a venit sa le scoata din castel, folosind harta pe care i-a dat-o zana buna. Pe harta sunt desenate cele n camere ale castelului, numerotate de la 1 la n si cele m tuneluri dintre camere. De asemenea sunt marcate camerele in care se gasesc fetele si Fat-Frumos, timpul necesar traversarii fiecarui tunel si cele p camere din care se poate iesi din castel.

Cerinta

Determinati timpul minim necesar lui Fat-Frumos pentru a lua cele 5 fete si a le scoate din castel.

Date de intrare

Pe prima linie a fisierului de intrare zmeu.in sunt scrise numerele n, m si p, reprezentand numarul de camere, numarul de tunele si respectiv numarul de iesiri din castel.
Pe a doua linie sunt scrise numerele a 6 camere distincte: primul numar e camera in care se afla Fat-Frumos, iar celelalte 5 sunt camerele fetelor.
Pe urmatoarele m linii sunt cate 3 numere, reprezentand cele m tunele: primele doua reprezinta camerele intre care face legatura tunelul, al treilea timpul necesar traversarii tunelului.
Ultimele p linii contin cate un numar reprezentand camerele din care se poate iesi din castel. Toate numerele sunt intregi strict pozitive, iar numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de iesire

Prima linie a fisierului zmeu.out va contine un singur numar, timpul minim necesar pentru a porni din camera lui Fat-Frumos, a trece prin camerele celor 5 fete si a ajunge intr-o camera care are iesire in afara. Se va lua in considerare numai timpul traversarii tunelurilor, neglijandu-se timpul traversarii camerelor sau a iesirii din castel. 

Restrictii

  • 4 <=n <= 1000
  • 1 <= m <= n*(n-1)/2
  • 1 <= p <= n/2
  • Timpul de traversare a unui tunel este un numar intreg din intervalul [1,200]
  • Initial in nici o camera nu se afla mai mult de o persoana.
  • Intotdeauna va exista o posibilitate de salvare a fetelor.

Exemplu

zmeu.in

zmeu.out

Explicatie
10 11 3
2 1 7 5 10 6
1 7 3
1 2 2
1 3 4
2 3 2
2 8 1
2 4 3
3 4 2
3 5 2
3 6 5
6 10 3
6 9 4
7
4
8
29 Un traseu posibil este:
2-1-7-1-2-3-5-3-6-10-6-3-4

prof. Nistor Mot
Colegiul National "N.Balcescu" Braila
Contact:emotz_ro@yahoo.co.uk

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: cursa, insule, termen, div, mese, hperm, chimie2, mere2, vile, dans, multiplu, paralel, divizor, ghici, barca1, fibo, parc, circular, sant, mobile, pattern, mutare, concurs2, soricel1, soricel2, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, pion, el, tort1, triunghi4, bile6, zmax
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, 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, 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, trafic, masina1, bomboane, traseu, litoral, lover, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
Despre generare: taste, pluricex, balbe, magic3, formule, grup, nr01, reteta2, playlist, pizza1, caramele, caini, tvshow, adevar, prime1, hexa, premii1, carti2, bile4, hof, matrx, cubinvers, arctir, guess, minmax, stele, tablou1, adunscad, sumprod, prisme, operatii1, expeval, triburi1, optim, patru, genab, dineu, cumpanit, nkd, relatii, wb
surse trimise | ajutor