Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-01 09:43:27.
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 varfuri. Fiecare arc al grafului are costul egal cu 1. Se dau, de asemenea, si doua varfuri X si Y.

Cerinta

Se cere determinarea celui mai scurt drum dintre varfurile 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 arc orientat de la varful i spre varful 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 varfurile X si Y. Linia a doua va contine o insiruire de varfuri, 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 varful A la varful B, se intelege o insiruire P de K varfuri, cu proprietatile:
    • P1 = A.
    • PK = B.
    • Exista arc 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 drum, 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?