Danciu: Pagină nouă: 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 ca...

2024-06-04T03:15:45Z

Pagină nouă: 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 ca...

New page

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>

3446 - Ateleport - Revision history