3446 - Ateleport

Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există N planete diferite și M canale bidirecţionale de transport de tipul (x, y, t) care îţi permit să te deplasezi de pe planeta x pe planeta y (sau invers) în t 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ă x pe orice altă planetă y în P secunde cu condiţia că ai putea ajunge pornind de pe planeta x pe planeta y folosind maxim L canale de transport.

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

Cerința

Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.

Date de intrare

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

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

Date de ieșire

Fișierul de ieșire ateleport.out va conține o singură valoare pe prima linie care reprezintă

timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.

Restricții și precizări

• 1 < N, M ≤ 10 000;
• 0 ≤ L, K ≤ 10;
• 1 < Ti , P ≤ 100 000;
• 1 < Xi , Yi ≤ N;
• între oricare două planete există cel mult un canal;
• pentru teste în valoare de 30 de puncte se garantează că K = 0 și toate canalele de comunicare au Ti = 1;
• pentru ALTE teste în valoare de 20 de puncte se garantează că K = 0;
• pentru ALTE teste în valoare de 20 de puncte se garantează că N ≤ 300;
• 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

ateleport.in

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

ateleport.out

14

Explicație

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

Exemplul 1

ateleport.in

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

ateleport.out

27

Explicație

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