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:

1. Să zboare de pe insula i pe o altă insulă x cu dragonul pe care îl are, folosind o rută directă j între insulele i si x, bineînțeles doar dacă Dj ≤ Dmaxt.
2. Să schimbe dragonul din specia t pe care îl are cu un dragon din specia i aflat 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 ≤ 800
• 1 ≤ M ≤ 6000
• 1 ≤ Dmaxi ≤ 50 000, pentru orice 1 ≤ i ≤ N.
• 1 ≤ Aj, Bj ≤ N, pentru orice 1 ≤ j ≤ M.
• 1 ≤ Dj ≤ 50 000, pentru orice 1 ≤ 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

<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>