0588 - Dijkstra

Cerința

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

Date de intrare

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

Date de ieșire

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

Restricții și precizări

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

Exemplul 1:

dijkstraIN.txt

5 4
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2

dijkstraOUT.txt

3 1 4 0 -1

Exemplul 2:

dijkstraIN.txt

1001 12
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2

dijkstraOUT.txt

"Datele nu corespund restrictiilor impuse"

Rezolvare

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