Simina: /* Date de ieșire */

2023-12-27T18:08:15Z

Date de ieșire

← Older revision		Revision as of 18:08, 27 December 2023
Line 6:		Line 6:

	= Date de ieșire =		= 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>.		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 =		= Restricții și precizări =

Simina: Pagină nouă: = 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`...

2023-12-27T18:01:54Z

Pagină nouă: = 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>...

New page

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

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

0588 - Dijkstra - Revision history

Simina: /* Date de ieșire */