Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bfs.in, bfs.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Florian Marcu •Florian |
| Timp execuţie pe test | 0.525 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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.
- Se garanteaza ca diagonala principala a matricei de adiacenta are toate elementele egale cu 0.
- Daca exista mai multe solutii, se poate afisa oricare.
Exemplu
| bfs.in | bfs.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) ?
