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 varfuri si M arce. 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 M X Y, cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x $y, cu semnificatia ca exista arc orientat de la x la y.

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 ≤ 1000 .
• 1 ≤ M ≤ min ( 100.000, N * ($N + 1 )/ 2 ).$
• X diferit de Y.
• Prin drum de la varful A la varful B, se intelege o insiruire P de K varfuri, cu proprietatile:
  • P₁ = A.
  • P_K = B.
  • Exista arc de la P_i la P_i+1, pentru orice i =1, K - 1.
  • P_i diferit de P_j , pentru orice i diferit de j.
• Daca intre X si Y nu exista niciun drum, se va afisa 0.
• Daca exista mai multe solutii, se poate afisa oricare.

Exemplu

Explicatie

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

Feedback Cosmin: de ce nu sunt n si m aici mult mai mari? Algoritmul de cautare in latime are complexitate O(n + m) si atunci ar merge date cu cateva ordine mai mari de marime decat cum sunt restrictiile acum.
Florian: Problema nu e inca finalizata. Nu e suficient 1000 de noduri si 100.000 de muchii?

Cum se trimit solutii?