The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

ateleport.out

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

ateleport.out

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>