View source for 3446 - Ateleport

Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există <code>N</code> planete diferite și <code>M</code> canale bidirecţionale de transport de tipul <code>(x, y, t)</code> care îţi permit să te deplasezi de pe planeta <code>x</code> pe planeta <code>y</code> (sau invers) în <code>t</code> secunde.

Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv care îți permite teleportarea de pe o planetă <code>x</code> pe orice altă planetă <code>y</code> în <code>P</code> secunde cu condiţia că ai putea ajunge pornind de pe planeta <code>x</code> pe planeta <code>y</code> folosind maxim <code>L</code> canale de transport.

Acest dispozitiv este momentan doar un prototip, așa că nu îl poate folosi mai mult de <code>K</code> ori. Marian se află pe planeta <code>1</code> și te roagă să îi spui care e timpul minim necesar pentru a ajunge pe planeta <code>N</code>.

= Cerința =
Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta <code>N</code> pornind de pe planeta <code>1</code>.

= Date de intrare =
Fișierul de intrare <code>ateleport.in</code> conține pe prima linie <code>5</code> valori <code>N</code>, <code>M</code>, <code>P</code>, <code>L</code>, <code>K</code>, separate printr-un singur spaţiu, cu semnificaţia din enunţ.

Pe fiecare din următoarele <code>M</code> linii se vor afla câte <code>3</code> valori <code>Xi</code>, <code>Yi</code>, <code>Ti</code> care descriu un canal de transport.

= Date de ieșire =
Fișierul de ieșire <code>ateleport.out</code> va conține o singură valoare pe prima linie care reprezintă

timpul minim necesar pentru a ajunge pe planeta <code>N</code> pornind de pe planeta <code>1</code>.

= Restricții și precizări =

* <code>1 < N, M ≤ 10 000</code>;
* <code>0 ≤ L, K ≤ 10</code>;
* <code>1 < Ti</code> <code>, P ≤ 100 000</code>;
* <code>1 < Xi</code> <code>, Yi ≤ N</code>;
* între oricare două planete există cel mult un canal;
* pentru teste în valoare de 30 de puncte se garantează că <code>K = 0</code> și toate canalele de comunicare au <code>Ti = 1</code>;
* pentru ALTE teste în valoare de 20 de puncte se garantează că <code>K = 0</code>;
* pentru ALTE teste în valoare de 20 de puncte se garantează că <code>N ≤ 300</code>;
* se garantează că pentru toate testele există soluţie;
* în concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

= Exemplul 1 =
<code>ateleport.in</code>
 6 7 3 2 1
 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>
 14

=== Explicație ===
Dispozitivul se poate folosi cel mult o dată. Pentru a ajunge pe planeta <code>6</code> în timp minim vom parcurge canalul <code>1 → 2</code> apoi ne vom teleporta până pe planeta <code>5</code> de unde vom mai parcurge canalul <code>5 → 6</code>. Costul final este <code>2 + 3</code>(teleportare)  <code>+ 9 = 14</code>.

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