Editing 0484 - Lant Minim

= Cerinţa =
Se dă lista muchiilor unui graf neorientat și două vârfuri <code>p q</code> . Să se determine cel mai scurt lanț cu extremitățile <code>p q</code>.

= Date de intrare =
Fişierul de intrare <code>lantminimIN.txt</code> conţine pe prima linie numerele <code>n p q</code>, 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 <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>lantminimOUT.txt</code> 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 =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* în fișierul de intrare muchiile se pot repeta;
* orice lanț de lungime minimă cu extremitățile <code>p q</code> este acceptat;
* pentru toate datele de test există cel puțin un lanț de la <code>p</code> la <code>q</code>;

= Exemplul 1 =
<code>lantminimIN.txt</code>
 6 2 6
 1 2
 1 3
 1 4
 3 4
 4 5
 4 6
 5 6
<code>lantminimOUT.txt</code>
 4
 2 1 4 6 

= Exemplul 2 =
<code>lantminimIN.txt</code>
 101 101 101
<code>lantminimOUT.txt</code>
 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

# 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)))

</syntaxhighlight>