Editing 0593 - Parc (section)

= Exemplul 2: =
<code>parcIN.txt</code>
 0 8 2
 1 2 4
 1 5 1
 1 7 2
 2 3 9
 2 4 2
 2 6 2
 2 7 1
 5 6 7
 2
 3 5
<code>parcOUt.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import heapq
import sys

MAX = 100

def citire_date():
    with open('parcIN.txt', 'r') as fin:
        n, m, C = map(int, fin.readline().strip().split())
        muchii = [dict() for _ in range(MAX + 1)]
        lungimi = [dict() for _ in range(MAX + 1)]
        for _ in range(m):
            i, j, L = map(int, fin.readline().strip().split())
            muchii[i][j] = muchii[j][i] = True
            lungimi[i][j] = lungimi[j][i] = L
        P = int(fin.readline().strip())
        p_list = list(map(int, fin.readline().strip().split()))
    return n, m, C, muchii, lungimi, P, p_list

def validare_restrictii(n, m, lungimi):
    if not (1 <= n <= 100):
        return False
    for nod in range(1, n+1):
        for lungime in lungimi[nod].values():
            if lungime >= 1000:
                return False
    return True

def dijkstra(n, muchii, lungimi, start):
    lenMin = [float('inf')] * (n + 1)
    lenMin[start] = 0
    heap = [(0, start)]
    while heap:
        current_len, node = heapq.heappop(heap)
        if current_len > lenMin[node]:
            continue
        for neighbor in muchii[node]:
            length = current_len + lungimi[node][neighbor]
            if length < lenMin[neighbor]:
                lenMin[neighbor] = length
                heapq.heappush(heap, (length, neighbor))
    return lenMin

def main():
    n, m, C, muchii, lungimi, P, p_list = citire_date()
    if not validare_restrictii(n, m, lungimi):
        with open('parcOUT.txt', 'w') as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return

    lenMinP = float('inf')
    pMin = -1
    for p in p_list:
        lenMin = dijkstra(n, muchii, lungimi, p)
        if lenMin[C] < lenMinP:
            lenMinP = lenMin[C]
            pMin = p

    with open('parcOUT.txt', 'w') as fout:
        fout.write(str(pMin))

if __name__ == "__main__":
    main()

</syntaxhighlight>