0484 - Lant Minim
De la Universitas MediaWiki
Cerinţa
Se dă lista muchiilor unui graf neorientat și două vârfuri p q
. Să se determine cel mai scurt lanț cu extremitățile p q
.
Date de intrare
Fişierul de intrare lantminimIN.txt
conţine pe prima linie numerele n p q
, reprezentând numărul de vârfuri ale grafului și cele două vârfuri date. Fiecare dintre următoarele linii conține câte o pereche de numere i j
, cu semnificația că există muchie între i
și j
.
Date de ieşire
Fişierul de ieşire lantminimOUT.txt
va conţine pe prima linie numărul de vârfuri din lanțul determinat. A doua linie va conține vârfurile din acest lanț, separate prin exact un spațiu.
Restricţii şi precizări
1 ≤ n ≤ 100
1 ≤ i , j ≤ n
- în fișierul de intrare muchiile se pot repeta;
- orice lanț de lungime minimă cu extremitățile
p q
este acceptat; - pentru toate datele de test există cel puțin un lanț de la
p
laq
;
Exemplul 1
lantminimIN.txt
6 2 6 1 2 1 3 1 4 3 4 4 5 4 6 5 6
lantminimOUT.txt
4 2 1 4 6
Exemplul 2
lantminimIN.txt
101 101 101
lantminimOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
import heapq
def dijkstra(graf, start, end):
# Inițializare distanțe și coadă de priorități
distante = {varf: float('infinity') for varf in graf}
distante[start] = 0
coada_prioritati = [(0, start)]
while coada_prioritati:
distanta_curenta, varf_curent = heapq.heappop(coada_prioritati)
# Verificare dacă am găsit un drum mai scurt
if distanta_curenta > distante[varf_curent]:
continue
for vecin, pondere in graf[varf_curent]:
distanta = distanta_curenta + pondere
# Actualizare distanțe și adăugare în coadă
if distanta < distante[vecin]:
distante[vecin] = distanta
heapq.heappush(coada_prioritati, (distanta, vecin))
# Construire lanț minim
drum_minim = []
varf_curent = end
while varf_curent != start:
drum_minim.insert(0, varf_curent)
varf_curent = graf[varf_curent][0][0] # Se folosește primul vecin în loc de [1]
drum_minim.insert(0, start)
return drum_minim
def verifica_restrictii(n, muchii, p, q):
# Verificare restricții
if not (1 <= n <= 100 and all(1 <= i <= n and 1 <= j <= n for i, j in muchii)):
return False
# Alte verificări specifice, dacă este cazul
return True
# Citire date din fișierul de intrare
with open("lantminimIN.txt", "r") as fisier:
n, p, q = map(int, fisier.readline().split())
muchii = [tuple(map(int, linie.split())) for linie in fisier.readlines()]
# Verificare restricții
if not verifica_restrictii(n, muchii, p, q):
with open("lantminimOUT.txt", "w") as fisier:
fisier.write("Datele nu corespund restrictiilor impuse")
else:
# Construire graf
graf = {i: [] for i in range(1, n + 1)}
for muchie in muchii:
graf[muchie[0]].append((muchie[1], 1))
graf[muchie[1]].append((muchie[0], 1))
# Aplicare algoritm Dijkstra
drum_minim = dijkstra(graf, p, q)
# Scriere rezultat în fișierul de ieșire
with open("lantminimOUT.txt", "w") as fisier:
fisier.write(str(len(drum_minim)) + "\n")
fisier.write(" ".join(map(str, drum_minim)))