Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Grafxy

Adăugată de :
sorynsoo
Sursă :
XOR2013
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
1000 ms
Limită memorie :
65536 kbytes

Fie un graf neorientat conex cu N vârfuri (numerotate de la 1 la N) şi M muchii. Se consideră de asemenea două mulţimi nevide X şi Y de vârfuri din acest graf, mulţimi care nu au vârfuri comune. Lungimea unui lanţ de la un vârf v1 la un vârf v2 este dată de numărul de muchii al lanţului. Definim distanţa de la un vârf v la mulţimea Y ca fiind lungimea minimă a unui lanţ de la vârful v la un vârf din mulţimea Y.

 

Cerinţa

Să se determine distanţa de la orice vârf din mulţimea X la mulţimea Y.

 

Date de intrare

Fişierul de intrare conţine pe prima linie numerele naturale N şi M separate prin spaţiu. Pe următoarele M linii se află câte două numere naturale i şi j separate prin spaţiu reprezentând extremităţile unei muchii din graf. Pe linia M + 2 se găseşte un număr natural nx reprezentând numărul de vârfuri ale mulţimii X. Pe linia M + 3 se găsesc, separate prin spaţii, nx numere naturale în ordine crescătoare x1, x2, ..., xnx reprezentând vârfurile grafului care aparţin mulţimii X. Pe linia M + 4 se găseşte un număr natural ny reprezentând numărul de vârfuri ale mulţimii Y. Pe linia M + 5 se găsesc, separate prin spaţii, ny numere naturale în ordine crescătoare y1, y2, ..., yny reprezentând vârfurile grafului care aparţin mulţimii Y.

 

Date de iesire

Fişierul de iesire va conţine exact nx linii. Pe linia i (i = 1..nx) se găseşte un singur număr natural reprezentând distanţa de la vârful xi la mulţimea Y.

 

Restricţii şi precizări:

  • 4 <= N <= 100 000
  • N – 1 <= M <= 300 000
  • 1 <= nx < N; 1 <= ny < N

 

Exemplu

Date de intrare

Date de iesire

Explicaţii

  7 8

  1 2

  2 3

  4 2

  4 5

  6 5

  7 3

  4 6

  7 6

  3

  1 2 3

  3

  5 6 7

  3

  2

  1

  Graful are 7 vârfuri şi 8 muchii

  

  X = {1, 2, 3}, iar Y = {5, 6, 7}.

  Distanţa de la vârful 1 la Y este 3, lanţul de lungime minimă fiind 1, 2, 4, 6 (deci 3 muchii).

  Distanţa de la vârful 2 la Y este 2 (lanţul 2, 4, 5 sau lanţul 2, 3, 7), iar distanţa de la vârful 3 la Y este 1 (lanţul 3, 7)


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Grafuri


Comentarii

Adauga un comentariu: Click !