1136 - Dragoni
Enunț[edit | edit source]
Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:
Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j intre 1 si M, ruta j unește insulele Aj și Bj și are lungime Dj.
Pe fiecare insulă i, (1 ≤ i ≤ n) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmaxi. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j, (1 ≤ j ≤ m) pentru care Dj ≤ Dmaxi, indiferent de ce alte drumuri au făcut anterior.
Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insula i, (1 ≤ i ≤ n) având cu el un dragon din specia t, el poate:
- Să zboare de pe insula
ipe o altă insulăxcu dragonul pe care îl are, folosind o rută directăjîntre insuleleisix, bineînțeles doar dacăDj ≤ Dmaxt. - Să schimbe dragonul din specia
tpe care îl are cu un dragon din speciaiaflat pe insula respectivă.
Cerințe[edit | edit source]
a. Să se determine distanța maxima Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.
Date de intrare[edit | edit source]
Fișierul de intrare dragoniIN.txt conține pe prima linie numărul p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se găsesc două numere naturale N și M reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc N numere naturale, al i-lea dintre acestea reprezentând distanta maximă Dmaxi pe care o poate zbura un dragon de pe insula i. Pe următoarele M linii sunt descrise cele M rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale A, B și D cu semnificația că există rută bidirecțională de lungime D între insulele A și B.
Date de ieșire[edit | edit source]
n fișierul de ieșire dragoniOUt.txt se va afișa un singur număr natural.
Dacă valoarea lui p este 1, se rezolvă numai cerința a.
În acest caz numărul afișat va reprezenta distanța maximă Dmaxi a unui dragon i la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
Daca valoarea lui p este 2, se va rezolva numai cerința b,
În acest caz numărul afișat va reprezenta distanța minima pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Restricții și precizări[edit | edit source]
1 ≤ N ≤ 8001 ≤ M ≤ 60001 ≤ Dmaxi ≤ 50 000, pentru orice1 ≤ i ≤ N.1 ≤ Aj, Bj ≤ N, pentru orice1 ≤ j ≤ M.1 ≤ Dj ≤ 50 000, pentru orice1 ≤ j ≤ M.- Se garantează că Hiccup poate ajunge pe insula
N. - Se garantează că răspunsul oricărei cerințe este un număr natural mai mic decât
109. - Pentru rezolvarea corectă a primei cerințe se acordă 20% din punctajul testului respectiv.
- Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 80% din punctajul testului respectiv.
Exemplul 1:[edit | edit source]
dragoniIN.txt
1 5 6 6 3 13 20 26 1 2 5 1 3 7 1 5 10 2 3 6 3 4 5 3 5 14
dragoniOUt.txt
20
Explicație[edit | edit source]
p = 1 deci se va rezolva cerința a).
Există N = 5 insule si M = 6 rute între ele. Hiccup pornește de pe insula 1 având un dragon care poate zbura o distanță de maxim 6. Cu acest dragon poate ajunge doar pe insulele 1, 2, 3 si 4, întrucât pentru a ajunge pe insula 5 el ar fi obligat sa parcurgă o ruta de lungime mai mare decât 6.
Distanta maxima pe care o poate zbura un dragon aflat pe insulele 1, 2, 3 sau 4 este deci 20 (dragonul de pe insula 4). Se observă că dragonul care poate zbura o distanță de 26 se afla pe insula 5 și este inaccesibil.
Exemplul 2:[edit | edit source]
dragoniIN.txt
1 801 6 6 3 13 20 26 1 2 5 1 3 7 1 5 10 2 3 6 3 4 5 3 5 14
dragoniOUt.txt
Datele nu corespund restrictiilor impuse
Rezolvare[edit | edit source]
<syntaxhighlight lang="python3" line="1"> import heapq
class Dij:
def __init__(self, nod, cost):
self.nod = nod
self.cost = cost
def __lt__(self, other):
return self.cost > other.cost
def validate_restrictions(n, m, dmax):
if not (1 <= n <= 800 and 1 <= m <= 6000):
return False
for i in range(1, n + 1):
if not (1 <= dmax[i] <= 50000):
return False
return True
with open("dragoniIN.txt", "r") as fin, open("dragoniOUT.txt", "w") as fout:
p = int(fin.readline())
if p == 1:
n, m = map(int, fin.readline().split())
dmax = [0] + list(map(int, fin.readline().split()))
if not validate_restrictions(n, m, dmax):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()
gf = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, fin.readline().split())
if not (1 <= a <= n and 1 <= b <= n and 1 <= c <= 50000):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()
gf[a].append((b, c))
gf[b].append((a, c))
q = []
max_val = dmax[1]
viz = [False] * (n + 1)
viz[1] = True
q.append(1)
while q:
nod = q.pop(0)
for nex in gf[nod]:
if nex[1] <= dmax[1] and not viz[nex[0]]:
viz[nex[0]] = True
max_val = max(max_val, dmax[nex[0]])
q.append(nex[0])
fout.write(str(max_val) + "\n")
elif p == 2:
n, m = map(int, fin.readline().split())
dmax = [0] + list(map(int, fin.readline().split()))
if not validate_restrictions(n, m, dmax):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()
cost = [[float('inf')] * (n + 1) for _ in range(n + 1)]
costmin = [[float('inf')] * (n + 1) for _ in range(n + 1)]
gf = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, fin.readline().split())
if not (1 <= a <= n and 1 <= b <= n and 1 <= c <= 50000):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()
gf[a].append((b, c))
gf[b].append((a, c))
for i in range(1, n + 1):
pq = []
heapq.heappush(pq, Dij(i, 0))
cost[i][i] = 0
while pq:
cur = heapq.heappop(pq)
nod, costc = cur.nod, cur.cost
if costc < cost[i][nod]:
continue
for nex in gf[nod]:
if nex[1] <= dmax[i] and costc + nex[1] < cost[i][nex[0]]:
cost[i][nex[0]] = costc + nex[1]
heapq.heappush(pq, Dij(nex[0], cost[i][nex[0]]))
class Stare:
def __init__(self, nod, cost, dragon):
self.nod = nod
self.cost = cost
self.dragon = dragon
q = []
q.append(Stare(1, 0, 1))
costfinalmin = float('inf')
costmin[1][1] = 0
while q:
cur = q.pop(0)
nod, costc, dragon = cur.nod, cur.cost, cur.dragon
if costc > costmin[dragon][nod]:
continue
for nex in gf[nod]:
if nex[1] <= dmax[dragon]:
nexcost = costc + nex[1]
nexdrag = dragon
if dmax[nex[0]] > dmax[dragon]:
nexdrag = nex[0]
elif dmax[nex[0]] == dmax[dragon]:
nexdrag = min(dragon, nex[0])
if nexcost >= costmin[nexdrag][nex[0]]:
continue
costmin[nexdrag][nex[0]] = nexcost
q.append(Stare(nex[0], nexcost, nexdrag))
costfinalmin = min(costfinalmin, costmin[nexdrag][nex[0]] + cost[nexdrag][nex[0]])
fout.write(str(costfinalmin) + "\n")
</syntaxhighlight>