1604 - D Min

From Bitnami MediaWiki

Enunț[edit | edit source]

Se consideră un graf neorientat conex cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu y.

Cerinţa[edit | edit source]

Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța minimă dintre x și y.

Date de intrare[edit | edit source]

Fişierul de intrare dminIN.txt conţine pe prima linie două numere n şi m, reprezentând numărul de noduri, respectiv numărul de muchii. Fiecare dintre următoarele m linii va conţine câte două numere x şi y, separate printr-un spaţiu, cu semnificaţia: există o muchie între nodul x şi nodul y.

Următoarea linie conține un număr k, iar următoarele k linii câte două numere x y.

Date de ieşire[edit | edit source]

Fişierul de ieşire dminOUT.txt va conţine k linii. Fiecare linie va conține distanța minimă dintre nodurile x y din fișierul de intrare, în ordinea din fișierul de intrare.

Restricţii şi precizări[edit | edit source]

  • n ≤ 100
  • k ≤ 100
  • pentru toate perechile x y există cel puțin un drum elementar de la x la y.

Exemplul 1[edit | edit source]

dminIN.txt

6 7
1 3
1 2
2 3
2 4
3 4
4 5
5 6
3
1 6
5 3
2 5

dminOUT.txt

4
2
2

Exemplul 2[edit | edit source]

dminIN.txt

101 101

dminOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def verificare_restrictii(n, k):

   if n > 100 or k > 100:
       return False
   return True

def bfs(GRAF, start, sfarsit):

   vizitate = set()
   coada = start
   if start == sfarsit:
       return 0
   while coada:
       drum = coada.pop(0)
       nod = drum[-1]
       if nod not in vizitate:
           vecini = GRAF[nod]
           for vecin in vecini:
               drum_nou = list(drum)
               drum_nou.append(vecin)
               coada.append(drum_nou)
               if vecin == sfarsit:
                   return len(drum_nou) - 1
           vizitate.add(nod)
   return -1  # Dacă nu există drum între noduri

def main():

   with open('dminIN.txt', 'r') as fisier_intrare:
       n, m = map(int, fisier_intrare.readline().split())
       if not verificare_restrictii(n, m):
           with open('dminOUT.txt', 'w') as fisier_iesire:
               fisier_iesire.write("Datele nu corespund restrictiilor impuse")
           return
       GRAF = {i: [] for i in range(1, n + 1)}
       for _ in range(m):
           x, y = map(int, fisier_intrare.readline().split())
           GRAF[x].append(y)
           GRAF[y].append(x)
       k = int(fisier_intrare.readline())
       interogari = [tuple(map(int, fisier_intrare.readline().split())) for _ in range(k)]
   with open('dminOUT.txt', 'w') as fisier_iesire:
       for interogare in interogari:
           x, y = interogare
           distanta = bfs(GRAF, x, y)
           fisier_iesire.write(str(distanta) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>