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

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


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

Gigel s-a hotarat sa face o calatorie prin tara sa. El vrea sa mearga pana intr-un oras destinatie iar apoi sa se intoarca in orasul din care a plecat. Pentru ca excursia sa nu devina prea monotona, Gigel a pus urmatoarea conditie: drumul de la dus si cel de la intoarcere trebuie sa contina un numar minim de sosele comune. (Nici drumul de la dus, nici cel de la intoarcere nu au voie sa parcurga aceeasi sosea de la multe ori).

Cerinta

Scrieti un program care sa-l ajute pe Gigel sa gaseasca un drum dus-intors care sa contina cat mai putine sosele comune.

Date de intrare

Pe prima linie a fisierul trip.in se afla 2 intregi S si D (S<>D) care reprezinta orasul de plecare si orasul destinatie. Urmatoarea linie contine 2 intregi N si M, unde N este numarul de orase si M este numarul de sosele. Urmatoarele M linii contin cate 2 intregi P si Q (1<=P<=N, 1<=Q<=N, P<>Q) cu semnificatia ca intre orasul P si orasul Q exista o sosea (pe care se poate merge in ambele sensuri). Orasele sunt numerotate de la 1 la N.

Date de iesire

Prima linie a fisierului trip.out trebuie sa contina un intreg care reprezinta numarul minum de sosele comune pe care le au cele doua drumuri. A doua linie trebuie sa contina o succesiune de noduri care reprezinta drumul de la S la D (succesiunea trebuie sa contina si S si D). A treia linie trebuie sa contina un drum de intoarcere de la D la S. Daca nu exista doua astfel de drumuri, fisierul de iesire va contine -1.

Restrictii

  • 3<=N<=1000
  • 2<=M<=100000
  • Cele doua drumuri descrise in fisierul de iesire trebuie sa includa orasul de plecare si cel de sosire
  • Daca exista mai multe perechi de drumuri care satisfac conditia impusa de Gigel, in fisierul de iesire se va scrie o singura pereche

Exemple

trip.in trip.out
1 6
7 8
2 1
1 3
2 3
4 2
4 5
5 6
7 5
6 7
2
1 3 2 4 5 7 6
6 5 4 2 1

Mod de punctare

Daca prima linie contine numarul corect de sosele comune, obtineti 2 puncte. Daca drumurile de pe liniile 2 si 3 sunt corecte, mai obtineti inca 3 puncte (deci 5 puncte in total). Daca prima linie este gresita nu primiti nici un punct (chiar daca cele doua drumuri sunt corecte).

Daniel Dumitran
Universitatea Politehnica Bucuresti

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, lover, 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: traseu, suma3, benzina, izo
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, 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, lover, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
Despre conexitate: arce, flood, matrice, shgraf, pact, echipe1, vitale, spion, bcolor, mexc, dep, fazan, cfr, chei, teme, entries, pamant, neconex, module, drumuri2, cristal, nuclee
surse trimise | ajutor