Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri și vârf `p` . Să se determine toate nodurile `q` ale grafului cu proprietatea că lungimea minimă a unui lanț de la `q` la `p` este `L`. = Date de intrare = Fişierul de intrare `lungimeminimaIN.txt` conţine pe prima linie numerele `n p L`, cu semnificația precizată. Fiecare dintre următoarele linii conține...

2023-12-13T13:44:06Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și vârf <code>p</code> . Să se determine toate nodurile <code>q</code> ale grafului cu proprietatea că lungimea minimă a unui lanț de la <code>q</code> la <code>p</code> este <code>L</code>. = Date de intrare = Fişierul de intrare <code>lungimeminimaIN.txt</code> conţine pe prima linie numerele <code>n p L</code>, cu semnificația precizată. Fiecare dintre următoarele linii conține...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și vârf <code>p</code> . Să se determine toate nodurile <code>q</code> ale grafului cu proprietatea că lungimea minimă a unui lanț de la <code>q</code> la <code>p</code> este <code>L</code>.

= Date de intrare =
Fişierul de intrare <code>lungimeminimaIN.txt</code> conţine pe prima linie numerele <code>n p L</code>, cu semnificația precizată. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>lungimeminimaOUT.txt</code> va conţine pe prima linie numărul de vârfuri determinate. A doua linie va conține în ordine crescătoare vârfurile determinate, separate prin exact un spațiu.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* în fișierul de intrare muchiile se pot repeta;
* pentru toate datele de test există cel puțin un vârf <code>q</code> cu proprietatea dorită;

= Exemplul 1 =
<code>lungimeminimaIN.txt</code>
7 4 2
1 2
1 7
1 4
3 5
4 5
4 7
5 6
5 7
<code>lungimeminimaOUT.txt</code>
3
2 3 6

= Exemplul 2 =
<code>lungimeminimaIN.txt</code>
101 101 101
<code>lungimeminimaOUT.txt</code>
Datele nu corespund restrictiilor impuse

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

def gaseste_noduri_cu_lungime_minima(graf, n, p, L):
vizitat = [False] * (n + 1)
noduri_rezultat = []

def bfs(nod, lungime_tinta):
coada = deque([(nod, 0)])
vizitat[nod] = True # Setăm nodul de pornire ca vizitat

while coada:
nod_curent, lungime_curenta = coada.popleft()

if lungime_curenta == lungime_tinta:
noduri_rezultat.append(nod_curent)

for vecin in graf[nod_curent]:
if not vizitat[vecin]:
vizitat[vecin] = True
coada.append((vecin, lungime_curenta + 1))

bfs(p, L)

return noduri_rezultat

def verificare_restrictii(n, i, j):
if not (1 <= n <= 100):
return False
if not (1 <= i <= n) or not (1 <= j <= n):
return False
return True

def main():
with open("lungimeminimaIN.txt", "r") as fisier_intrare:
n, p, L = map(int, fisier_intrare.readline().split())

# Verificare restricții
if not verificare_restrictii(n, p, L):
with open("lungimeminimaOUT.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(n):
muchie = tuple(map(int, fisier_intrare.readline().split()))
if not verificare_restrictii(n, muchie[0], muchie[1]):
with open("lungimeminimaOUT.txt", "w") as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
return
graf[muchie[0]].append(muchie[1])
graf[muchie[1]].append(muchie[0])

noduri_rezultat = gaseste_noduri_cu_lungime_minima(graf, n, p, L)

with open("lungimeminimaOUT.txt", "w") as fisier_iesire:
fisier_iesire.write(str(len(noduri_rezultat)) + "\n")
fisier_iesire.write(" ".join(map(str, sorted(noduri_rezultat))))

if __name__ == "__main__":
main()

</syntaxhighlight>

0538 - Lungime Minima - Revision history