Editing 3446 - Ateleport (section)

= Exemplul 1 =
<code>ateleport.in</code>
 6 7 3 2 0
 1 2 2
 1 3 5
 2 3 4
 2 4 23
 3 4 6
 5 4 7
 5 6 9
<code>ateleport.out</code>
 27

=== Explicație ===
Dispozitivul nu se poate folosi deloc. Pentru a ajunge pe planeta <code>6</code> de pe planeta <code>1</code> în timp minim, se vor parcurge canalele în ordinea <code>1→3→4→5→6</code> și se obține timpul <code>5+6+7+9=27</code> de secunde.

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

fin = open("ateleport.in", "r")
fout = open("ateleport.out", "w")

NMAX = 10001
TMAX = 11

class Muchie:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost

muchii = [[] for _ in range(NMAX)]
timp = [[[float('inf') for _ in range(TMAX)] for _ in range(TMAX)] for _ in range(NMAX)]

def ini(n):
    for i in range(1, n + 1):
        for j in range(11):
            for k in range(11):
                timp[i][j][k] = float('inf')

class Element:
    def __init__(self, nod, tp, p):
        self.nod = nod
        self.tp = tp
        self.p = p

    def __lt__(self, other):
        return timp[other.nod][other.tp][other.p] < timp[self.nod][self.tp][self.p]

def dijkstra(destinatie, l, k, p):
    timp[1][0][0] = 0
    pq = []
    heapq.heappush(pq, Element(1, 0, 0))

    while pq:
        relax = heapq.heappop(pq)

        for it in muchii[relax.nod]:
            # nu ma teleportez
            if timp[it.to][relax.tp][0] > timp[relax.nod][relax.tp][relax.p] + it.cost:
                timp[it.to][relax.tp][0] = timp[relax.nod][relax.tp][relax.p] + it.cost
                heapq.heappush(pq, Element(it.to, relax.tp, 0))

            # incep o teleportare
            if relax.tp < k:
                if timp[it.to][relax.tp + 1][1] > timp[relax.nod][relax.tp][relax.p] + p:
                    timp[it.to][relax.tp + 1][1] = timp[relax.nod][relax.tp][relax.p] + p
                    heapq.heappush(pq, Element(it.to, relax.tp + 1, 1))

            # continui o teleportare
            if relax.p and relax.p < l:
                if timp[it.to][relax.tp][relax.p + 1] > timp[relax.nod][relax.tp][relax.p]:
                    timp[it.to][relax.tp][relax.p + 1] = timp[relax.nod][relax.tp][relax.p]
                    heapq.heappush(pq, Element(it.to, relax.tp, relax.p + 1))

    ans = float('inf')
    for j in range(k + 1):
        for m in range(l + 1):
            ans = min(ans, timp[destinatie][j][m])

    fout.write(str(ans) + '\n')

if __name__ == "__main__":
    n, m, p, l, k = map(int, fin.readline().split())
    ini(n)

    for _ in range(m):
        a, b, c = map(int, fin.readline().split())
        muchii[a].append(Muchie(b, c))
        muchii[b].append(Muchie(a, c))

    dijkstra(n, l, k, p)

    fin.close()
    fout.close()

</syntaxhighlight>