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

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