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