0484 - Lant Minim

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 la q;

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

<syntaxhighlight lang="python3" line="1"> 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

1. 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()]

1. 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)))

</syntaxhighlight>