4074 - Distante

Enunț

Se consideră un graf neorientat conex cu n noduri, 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

Se dă o pereche de noduri p q. Determinați nodurile r cu proprietatea că distanța minimă dintre p și r este egală cu distanța minimă dintre r și q.

Date de intrare

Fişierul de intrare distanteIN.txt conţine pe prima linie numere n m p q. 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.

Date de ieşire

Fişierul de ieşire distanteOUT.txt va conține pe prime linie, separate prin câte un spațiu, modurile cerute în ordine crescătoare.

Restricţii şi precizări

• n ≤ 1000

Exemplul 1

distanteIN.txt

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

distanteOUT.txt

3 6 7 

Exemplul 2

distanteIN.txt

1001 86 37 3

distanteOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> from collections import deque

def bfs(graf, start):

   distante = {nod: float('inf') for nod in graf}
   distante[start] = 0
   coada = deque([start])

   while coada:
       nod_curent = coada.popleft()

       for vecin in graf[nod_curent]:
           if distante[vecin] == float('inf'):
               distante[vecin] = distante[nod_curent] + 1
               coada.append(vecin)

   return distante

def gaseste_noduri_potrivite(graf, p, q):

   distante_p = bfs(graf, p)
   distante_q = bfs(graf, q)

   noduri_potrivite = []
   for nod in graf:
       if distante_p[nod] == distante_q[nod]:
           noduri_potrivite.append(nod)

   return noduri_potrivite

def main():

   with open("distanteIN.txt", "r") as fisier_intrare:
       n, m, p, q = map(int, fisier_intrare.readline().split())

       if n > 1000:
           with open("distanteOUT.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)

   noduri_potrivite = gaseste_noduri_potrivite(graf, p, q)

   with open("distanteOUT.txt", "w") as fisier_iesire:
       if n <= 1000:
           fisier_iesire.write(" ".join(map(str, noduri_potrivite)))
       else:
           fisier_iesire.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":

   main()

</syntaxhighlight>