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

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


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

Zăhărel şi Sică s-au gândit să se reinventeze din punct de vedere spiritual. În prima fază, vor să se mute în oraşul Sala. Oraşul Sala conţine N case (numerotate de la 1 la N) unite prin M străzi bidirecţionale de lungimi egale. Ei au la dispoziţie fonduri limitate şi pot să se mute doar într-un cartier mărginaş format din X case. Fiindcă sunt buni prieteni cei doi vor să se mute în două case distincte, cât mai apropiate între ele.

Cerinţă

Determinaţi distanţa minimă dintre două case distincte dintre cele X din cartier.

Date de intrare

Pe prima linie a fişierului de intrare reinvent.in se află trei numere întregi N M X separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii se află câte două numere întregi distincte separate printr-un singur spaţiu, reprezentând o stradă bidirecţională din oraş. Ultima linie din fişier conţine X numere naturale distincte separate prin câte un spaţiu, reprezentând casele din cartier.

Date de ieşire

În fişierul de iesire reinvent.out se află un singur număr natural, reprezentând distanţa minimă între două case distincte din cartier.

Restricţii

1 ≤ N, M ≤ 100.000
2 ≤ X ≤ N

Pentru 30% din teste N ≤ 1024
Distanţa între două case se măsoară prin numărul minim de străzi necesare pentru a ajunge de la o casă la cealaltă
Între oricare două case există cel mult o stradă bidirecţională.
Există cel puţin două case din cartier astfel încât să existe drum între ele

Exemple

reinvent.inreinvent.outExplicaţii
5 6 2 1 2 2 3 2 4 3 4 1 4 3 5 1 5 3 Distanţa minimă între casele 1 şi 5 din cartier este 3. Un drum posibil format din 3 străzi este 1 – 2 – 3 – 5.

autor: Mircea Paşoi
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2009: bile, checkin, numere, text, reactii, volei, magic2, sirag, taste, tetris, origami, rafturi, joc2, br, perspic, tir, patrate2, nrcuv2, matrice, patrate1, pikachu, taxe, cartonas, case, desen2
De acelaşi autor: copaci, ab2, plimbare, cuvinte, pioni, numere3, perm, criptare, sume, gramezi, nr2, rev, paintball, matricea, emax, turism, puncte1, casute, dep
Despre coada: balanta, inginer, camp, rebus, harta, insule, volei, lbd, magic3, axa, cadere, ocean14, iepuras2, sah, balls, cd, toys, radio, caini, subperm, castel, excursia, casute, soricel2, masina2, salvare, paianjen, suma2, garaj, alee, lanterna, rj, caraibe, taxe1, sotron1, lanturi, tom, k1, dreptunghiuri, sokoban, ny, oldest, drumuri1, alpinist, tsunami, robot3, joc19, valet, oras1, gheizere, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, 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, 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
surse trimise | ajutor