Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-02 23:22:53.
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 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 ≤ Mmin ( 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:
    • 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.
  • 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 7 1 5
1 2
2 3
2 4
3 2
3 5
4 3
4 5
4
1 2 3 5

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?
astronomy: am lasat si eu un feedback sa fie data la n+m, cine l-a sters?:) Florian, daca dai N=1000 de noduri o sa intre N^2
Florian: Scuze. Eu l`am sters. Crezusem ca rezolvasem daca am marit N de la 100 la 1000. A fost neatentia mea. Voi pune N=100.000 si M=200.000.
Cosmin O sugestie: da testele gradat, pana la n = 1000 50 de puncte ca sa poata face toata lumea cu matrice de adiacenta in O(n^2). Si restul de 50 de puncte cu n si m mari ca sa trebuiasca sa folosesti liste de vecini si sa faci algoritmul in O(n + m).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?