Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-01 09:41:18.
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 test0.525 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 diferit de Pj , pentru orice i diferit de j.
  • Distanta de la un varf la el insusi este egala cu 0.
  • Daca intre X si Y nu exista niciun lant, se va afisa 0.
  • Daca exista mai multe solutii, se poate afisa oricare.

Exemplu

bfs.inbfs.out
5 1 5
0 1 0 0 0
0 0 1 1 0
0 1 0 0 1
0 0 1 0 1
0 0 0 0 0
4
1 2 3 5

Explicatie

Un alt drum de lugime 4 poate fi 1 2 4 5. Un alt drum posibil de la nodul 1 la nodul 5 este 1 2 4 3 5, dar acesta nu are lungime minima.

feedback astronomy: nu ar trebui data la O(N+M) ?

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?