Editing 0588 - Dijkstra

= Cerința =
Se dă un graf orientat ponderat cu <code>n</code> noduri – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod <code>p</code>. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la <code>p</code> la fiecare nod al grafului.

= Date de intrare =
Fișierul de intrare <code>dijkstraIN.txt</code> conține pe prima linie numerele <code>n p</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există arcul <code>(i j)</code> și are costul <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>dijkstraOUT.txt</code> va conține pe prima linie <code>n</code> numere, separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând costul drumului minim de la <code>p</code> la <code>i</code>. Dacă nu există drum de la <code>p</code> la un anumit vârf, costul afișat va fi <code>-1</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* costul unui arc va fi mai mic decât <code>1000</code>
* costul unui drum este egal cu suma costurilor arcelor care îl compun

= Exemplul 1: =
<code>dijkstraIN.txt</code>
 5 4
 1 3 1
 2 1 2
 4 2 1
 4 3 8
 5 3 5
 5 4 2
<code>dijkstraOUT.txt</code>
 3 1 4 0 -1

= Exemplul 2: =
<code>dijkstraIN.txt</code>
 1001 12
 1 3 1
 2 1 2
 4 2 1
 4 3 8
 5 3 5
 5 4 2
<code>dijkstraOUT.txt</code>
 "Datele nu corespund restrictiilor impuse"

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

def dijkstra(graph, start):
    n = len(graph)
    INF = float('inf')
    distante = [INF] * n
    distante[start] = 0
    heap = [(0, start)]

    while heap:
        dist_curenta, nod_curent = heapq.heappop(heap)

        if dist_curenta > distante[nod_curent]:
            continue

        for vecin, cost in graph[nod_curent]:
            distanta_noua = dist_curenta + cost
            if distanta_noua < distante[vecin]:
                distante[vecin] = distanta_noua
                heapq.heappush(heap, (distanta_noua, vecin))

    return distante

def verificare_restrictii(n, graph):
    # Verificarea restrictiilor
    if not (1 <= n <= 100):
        return False
    for node_edges in graph:
        for _, cost in node_edges:
            if not (cost < 1000):
                return False
    return True

def citeste_intrare(file_path):
    with open(file_path, 'r') as file:
        n, p = map(int, file.readline().split())
        
        # Verificare restrictii
        if not (1 <= n <= 100):
            return n, p, None

        graf = [[] for _ in range(n)]

        for _ in range(n):
            i, j, c = map(int, file.readline().split())
            graf[i-1].append((j-1, c))

    return n, p, graf

def scrie_iesire(file_path, distante, restrictii_valide):
    with open(file_path, 'w') as file:
        if not restrictii_valide:
            file.write("Datele nu corespund restrictiilor impuse")
        else:
            for dist in distante:
                if dist == float('inf'):
                    file.write("-1 ")
                else:
                    file.write(str(dist) + " ")

def main():
    fisier_intrare = 'dijkstraIN.txt'
    fisier_iesire = 'dijkstraOUT.txt'

    n, p, graf = citeste_intrare(fisier_intrare)

    # Verificare restricții
    restrictii_valide = verificare_restrictii(n, graf)

    if not restrictii_valide:
        # Dacă restricțiile nu sunt respectate, scrie mesajul în fișierul de ieșire
        scrie_iesire(fisier_iesire, [], restrictii_valide)
    else:
        # Altfel, aplică algoritmul lui Dijkstra și scrie rezultatele în fișierul de ieșire
        distante = dijkstra(graf, p-1)
        scrie_iesire(fisier_iesire, distante, restrictii_valide)

if __name__ == "__main__":
    main()

</syntaxhighlight>