Simina: /* Date de ieșire */

2023-12-27T18:08:37Z

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 =
	Programul va afișa <code>n</code> numere separate printr-un spațiu, al <code>i</code>-lea număr reprezentând distanța minimă de la casa lui Vlad la casa <code>i</code>.		Programul va afișa <code>n</code> numere separate printr-un spațiu, al <code>i</code>-lea număr reprezentând distanța minimă de la casa lui Vlad la casa <code>i</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 = Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt `n` case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa `p`, casa lui Vlad, și casele vecinilo...

2023-12-27T18:07:11Z

Pagină nouă: = Cerința = Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt <code>n</code> case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa <code>p</code>, casa lui Vlad, și casele vecinilo...

New page

= Cerința =
Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt <code>n</code> case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa <code>p</code>, casa lui Vlad, și casele vecinilor. În cazul în care nu există drum până la unul dintre vecini, se va afișa <code>-1</code>.

= Date de intrare =
Programul citește din fișier numărul <code>n</code>, numărul de case din comunitate, <code>m</code>, numărul de drumuri dintre case, <code>p</code>, numărul casei lui Vlad, iar pe următoarele <code>m</code> linii se vor afla <code>x</code>, <code>y</code> și <code>d</code> cu semnificația că există drum între casele <code>x</code> și <code>y</code> de lungime <code>d</code>.

= Date de ieșire =
Programul va afișa <code>n</code> numere separate printr-un spațiu, al <code>i</code>-lea număr reprezentând distanța minimă de la casa lui Vlad la casa <code>i</code>.

= Restricții și precizări =

* <code>1 ≤ p ≤ n ≤ 100.000</code>
* <code>1 ≤ m ≤ 250.000</code>
* cele <code>m</code> distanțe citite vor fi mai mici decât <code>20.000</code>

= Exemplul 1: =
<code>dijkstra2IN.txt</code>
5 6 2
3 5 1
5 4 9
4 3 5
1 2 2
3 2 2
1 3 8
<code>dijkstra2OUT.txt</code>
2 0 2 7 3

=== Explicație ===
Drumurile minime de la casa lui Vlad la celelalte case sunt <code>2 0 2 7 3</code>.

== Exemplul 2: ==
<code>dijkstra2IN.txt</code>
10000000 22 44
3 5 1
5 4 9
4 3 5
1 2 2
3 2 2
1 3 8
<code>dijkstra2OUT.txt</code>
Datele nu corespund restrictiilor impuse

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

def dijkstra(n, m, p, drumuri):
graf = {i: [] for i in range(1, n+1)}

for drum in drumuri:
x, y, d = drum
graf[x].append((y, d))
graf[y].append((x, d))

distante = {i: float('inf') for i in range(1, n+1)}
distante[p] = 0
coada_prioritati = [(0, p)]

while coada_prioritati:
distanta_curenta, nod_curent = heapq.heappop(coada_prioritati)

if distanta_curenta > distante[nod_curent]:
continue

for vecin, cost_muchie in graf[nod_curent]:
distanta_noua = distante[nod_curent] + cost_muchie

if distanta_noua < distante[vecin]:
distante[vecin] = distanta_noua
heapq.heappush(coada_prioritati, (distanta_noua, vecin))

return distante

def verifica_restrictii(n, m, p, drumuri):
if not (1 <= p <= n <= 100000) or not (1 <= m <= 250000):
return False

for drum in drumuri:
if drum[2] >= 20000:
return False

return True

# Citire date de intrare din fișier
with open('dijkstra2IN.txt', 'r') as fisier_intrare:
n, m, p = map(int, fisier_intrare.readline().split())
drumuri = [list(map(int, fisier_intrare.readline().split())) for _ in range(m)]

# Verificare restricții
if not verifica_restrictii(n, m, p, drumuri):
with open('dijkstra2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
else:
# Calculare distanțe minime
distante = dijkstra(n, m, p, drumuri)

# Afisare rezultat în fișier
with open('dijkstra2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write(' '.join(map(str, [distante[i] if distante[i] != float('inf') else -1 for i in range(1, n+1)])))

</syntaxhighlight>

1887 - Dijkstra2 - Revision history

Simina: /* Date de ieșire */