Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-29 06:28:48.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:bfs.in, bfs.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deFlorianFlorian Marcu Florian
Timp execuţie pe test1.05 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

BFS - Parcurgere in latime

Se considera un graf orientat cu N noduri. Fiecare muchie a grafului are costul egal cu 1. Se dau, de asemenea, si doua noduri X si Y.

Cerinta

Se cere determinarea celui mai scurt drum dintre nodurile X si Y.

Date de intrare

Fisierul de intrare bfs.in contine pe prima linie N X Y, cu semnificatia din enunt. Urmatoarele N linii contin cate N numere, reprezentand matricea de adiacenta a grafului. Cu alte cuvinte, al j-lea element de pe linia i+1 este egal cu 1, daca exista muchie orientata de la i spre j, respectiv 0 in caz contrar.

Date de iesire

In fisierul de iesire bfs.out va fi afisata pe prima linie lungimea celui mai scurt drum dintre nodurile X si Y. Linia a doua va contine o insiruire de noduri, reprezentand unul din drumurile de lungime minima dintre cele doua varfuri date, separate prin cate un spatiu.

Restrictii

  • 2 ≤ n ≤ 100 .
  • Prin drum de la nodul A la nodul B, se intelege o insiruire P de K noduri, cu proprietatile:
    • P1 = A.
    • PK = B.
    • Exista muchie de la Pi la Pi+1, pentru orice i =1, K - 1.
    • Pi = Pj , i == j.
  • Daca exista mai multe solutii, se poate afisa oricare.

Exemplu

bfs.inbfs.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?