Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-29 06:27:41.
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.

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?