1136 - Dragoni
Enunț
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
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
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
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
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:
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
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:
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
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")
