Editing 1136 - Dragoni (section)

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

class Dij:
    def __init__(self, nod, cost):
        self.nod = nod
        self.cost = cost

    def __lt__(self, other):
        return self.cost > other.cost

def validate_restrictions(n, m, dmax):
    if not (1 <= n <= 800 and 1 <= m <= 6000):
        return False
    
    for i in range(1, n + 1):
        if not (1 <= dmax[i] <= 50000):
            return False
    
    return True

with open("dragoniIN.txt", "r") as fin, open("dragoniOUT.txt", "w") as fout:
    p = int(fin.readline())
    
    if p == 1:
        n, m = map(int, fin.readline().split())
        dmax = [0] + list(map(int, fin.readline().split()))

        if not validate_restrictions(n, m, dmax):
            fout.write("Datele nu corespund restrictiilor impuse\n")
            exit()

        gf = [[] for _ in range(n + 1)]

        for _ in range(m):
            a, b, c = map(int, fin.readline().split())
            if not (1 <= a <= n and 1 <= b <= n and 1 <= c <= 50000):
                fout.write("Datele nu corespund restrictiilor impuse\n")
                exit()
            gf[a].append((b, c))
            gf[b].append((a, c))

        q = []
        max_val = dmax[1]
        viz = [False] * (n + 1)
        viz[1] = True
        q.append(1)

        while q:
            nod = q.pop(0)

            for nex in gf[nod]:
                if nex[1] <= dmax[1] and not viz[nex[0]]:
                    viz[nex[0]] = True
                    max_val = max(max_val, dmax[nex[0]])
                    q.append(nex[0])

        fout.write(str(max_val) + "\n")

    elif p == 2:
        n, m = map(int, fin.readline().split())
        dmax = [0] + list(map(int, fin.readline().split()))

        if not validate_restrictions(n, m, dmax):
            fout.write("Datele nu corespund restrictiilor impuse\n")
            exit()

        cost = [[float('inf')] * (n + 1) for _ in range(n + 1)]
        costmin = [[float('inf')] * (n + 1) for _ in range(n + 1)]
        gf = [[] for _ in range(n + 1)]

        for _ in range(m):
            a, b, c = map(int, fin.readline().split())
            if not (1 <= a <= n and 1 <= b <= n and 1 <= c <= 50000):
                fout.write("Datele nu corespund restrictiilor impuse\n")
                exit()
            gf[a].append((b, c))
            gf[b].append((a, c))

        for i in range(1, n + 1):
            pq = []
            heapq.heappush(pq, Dij(i, 0))
            cost[i][i] = 0

            while pq:
                cur = heapq.heappop(pq)
                nod, costc = cur.nod, cur.cost

                if costc < cost[i][nod]:
                    continue

                for nex in gf[nod]:
                    if nex[1] <= dmax[i] and costc + nex[1] < cost[i][nex[0]]:
                        cost[i][nex[0]] = costc + nex[1]
                        heapq.heappush(pq, Dij(nex[0], cost[i][nex[0]]))

        class Stare:
            def __init__(self, nod, cost, dragon):
                self.nod = nod
                self.cost = cost
                self.dragon = dragon

        q = []
        q.append(Stare(1, 0, 1))
        costfinalmin = float('inf')
        costmin[1][1] = 0

        while q:
            cur = q.pop(0)
            nod, costc, dragon = cur.nod, cur.cost, cur.dragon

            if costc > costmin[dragon][nod]:
                continue

            for nex in gf[nod]:
                if nex[1] <= dmax[dragon]:
                    nexcost = costc + nex[1]
                    nexdrag = dragon
                    if dmax[nex[0]] > dmax[dragon]:
                        nexdrag = nex[0]
                    elif dmax[nex[0]] == dmax[dragon]:
                        nexdrag = min(dragon, nex[0])

                    if nexcost >= costmin[nexdrag][nex[0]]:
                        continue

                    costmin[nexdrag][nex[0]] = nexcost
                    q.append(Stare(nex[0], nexcost, nexdrag))

                    costfinalmin = min(costfinalmin, costmin[nexdrag][nex[0]] + cost[nexdrag][nex[0]])

        fout.write(str(costfinalmin) + "\n")



</syntaxhighlight>