1604 - D Min
Enunț
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
Se dau k
perechi de vârfuri x y
. Determinați pentru fiecare pereche distanța minimă dintre x
și y
.
Date de intrare
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
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
n ≤ 100
k ≤ 100
- pentru toate perechile
x y
există cel puțin un drum elementar de lax
lay
.
Exemplul 1
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
dminIN.txt
101 101
dminOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
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()