1136 - Dragoni - Revision history

Rus Marius: Pagină nouă: == 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 2024-01-06T22:05:33Z Pagină nouă: == 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ă <code>N</code> insule. Hiccup, șeful tribului de vikingi aflat pe insula <code>1</code>, știe <code>M</code> rute directe de zbor bidirecționale între insule. Pentru fiecare <code>j</code> intre <code>1</code> si <code>M</cod... New page == 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ă <code>N</code> insule. Hiccup, șeful tribului de vikingi aflat pe insula <code>1</code>, știe <code>M</code> rute directe de zbor bidirecționale între insule. Pentru fiecare <code>j</code> intre <code>1</code> si <code>M</code>, ruta <code>j</code> unește insulele <code>Aj</code> și <code>Bj</code> și are lungime <code>Dj</code>. Pe fiecare insulă <code>i</code>, (<code>1 ≤ i ≤ n</code>) există dragoni din specia <code>i</code> care pot zbura fără a se opri pentru odihnă o distanță maximă <code>Dmaxi</code>. Cu alte cuvinte, dragonii de pe insula <code>i</code> vor putea parcurge orice rută <code>j</code>, (<code>1 ≤ j ≤ m</code>) pentru care <code>Dj ≤ Dmaxi</code>, indiferent de ce alte drumuri au făcut anterior. Hiccup dorește să ajungă de pe insula <code>1</code> pe insula <code>N</code> pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia <code>1</code> (de pe insula <code>1</code>). Apoi, dacă la un moment dat Hiccup se află pe o insula <code>i</code>, (<code>1 ≤ i ≤ n</code>) având cu el un dragon din specia <code>t</code>, el poate: # Să zboare de pe insula <code>i</code> pe o altă insulă <code>x</code> cu dragonul pe care îl are, folosind o rută directă <code>j</code> între insulele <code>i</code> si <code>x</code>, bineînțeles doar dacă <code>Dj ≤ Dmaxt</code>. # Să schimbe dragonul din specia <code>t</code> pe care îl are cu un dragon din specia <code>i</code> aflat pe insula respectivă. = Cerințe = a. Să se determine distanța maxima <code>Dmaxi</code> caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula <code>1</code>. b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula <code>1</code> pe insula <code>N</code>. = Date de intrare = Fișierul de intrare <code>dragoniIN.txt</code> conține pe prima linie numărul <code>p</code>. Pentru toate testele de intrare, numărul <code>p</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>. Pe a doua linie se găsesc două numere naturale <code>N</code> și <code>M</code> reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc <code>N</code> numere naturale, al <code>i</code>-lea dintre acestea reprezentând distanta maximă <code>Dmaxi</code> pe care o poate zbura un dragon de pe insula <code>i</code>. Pe următoarele <code>M</code> linii sunt descrise cele <code>M</code> rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale <code>A</code>, <code>B</code> și <code>D</code> cu semnificația că există rută bidirecțională de lungime <code>D</code> între insulele <code>A</code> și <code>B</code>. = Date de ieșire = n fișierul de ieșire <code>dragoniOUt.txt</code> se va afișa un singur număr natural. Dacă valoarea lui <code>p</code> este <code>1</code>, se rezolvă numai cerința a. În acest caz numărul afișat va reprezenta distanța maximă <code>Dmaxi</code> a unui dragon <code>i</code> la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula <code>1</code>. Daca valoarea lui <code>p</code> este <code>2</code>, 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 <code>1</code> pe insula <code>N</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse". = Restricții și precizări = * <code>1 ≤ N ≤ 800</code> * <code>1 ≤ M ≤ 6000</code> * <code>1 ≤ Dmaxi ≤ 50 000</code>, pentru orice <code>1 ≤ i ≤ N</code>. * <code>1 ≤ Aj, Bj ≤ N</code>, pentru orice <code>1 ≤ j ≤ M</code>. * <code>1 ≤ Dj ≤ 50 000</code>, pentru orice <code>1 ≤ j ≤ M</code>. * Se garantează că Hiccup poate ajunge pe insula <code>N</code>. * Se garantează că răspunsul oricărei cerințe este un număr natural mai mic decât <code>109</code>. * 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: = <code>dragoniIN.txt</code> 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 <code>dragoniOUt.txt</code> 20 = Explicație = <code>p = 1</code> deci se va rezolva cerința a). Există <code>N = 5</code> insule si <code>M = 6</code> rute între ele. Hiccup pornește de pe insula <code>1</code> având un dragon care poate zbura o distanță de maxim <code>6</code>. Cu acest dragon poate ajunge doar pe insulele <code>1</code>, <code>2</code>, <code>3</code> si <code>4</code>, întrucât pentru a ajunge pe insula <code>5</code> el ar fi obligat sa parcurgă o ruta de lungime mai mare decât <code>6</code>. Distanta maxima pe care o poate zbura un dragon aflat pe insulele <code>1</code>, <code>2</code>, <code>3</code> sau <code>4</code> este deci <code>20</code> (dragonul de pe insula <code>4</code>). Se observă că dragonul care poate zbura o distanță de <code>26</code> se afla pe insula 5 și este inaccesibil. == Exemplul 2: == <code>dragoniIN.txt</code> 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 <code>dragoniOUt.txt</code> Datele nu corespund restrictiilor impuse == Rezolvare == <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>