Editing 4078 - Distanta (section)

= Exemplul 2: =
<code>distantaIN.txt</code>
 22
 Bistrita 14
 Oradea 80
 Beius 7
 Galatii-Bistritei 1
 Reghin 3
 Sibiu 15
 Cluj-Napoca 30
 10
 Bistrita Oradea 223
 Cluj-Napoca Sibiu 119
 Bistrita Cluj-Napoca 100
 Beius Oradea 50
 Bistrita Galatii-Bistritei 15
 Reghin Galatii-Bistritei 35
 Oradea Cluj-Napoca 100
 Sibiu Reghin 154
 Beius Sibiu 130
 Reghin Cluj-Napoca 133
 Bistrita Beius
<code>distantaOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from queue import Queue

Inf = 0x3f3f3f3f

def check_restrictions(n, m, codif):
    if not (1 < n < 21) or not (0 <= m <= 190):
        return False

    for _, _, s in codif:
        if not (0 < len(s) < 21):
            return False

    return True
if __name__ == "__main__":
    with open("distantaIN.txt", "r") as infile, open("distantaOUT.txt", "w") as outfile:
        n = int(infile.readline().strip())
        codif = []
        G = [[] for _ in range(51)]
        t = [0] * 51
        timp = [0] * 51

        if not (1 < n < 21):
            outfile.write("Datele nu corespund restrictiilor impuse")
        else:
            for i in range(1, n + 1):
                line = infile.readline().split()
                if len(line) != 2:
                    outfile.write("Datele nu corespund restrictiilor impuse")
                    break

                s, cost = line
                cost = int(cost)
                codif.append((i, cost, s))

            m = int(infile.readline().strip())

            if not (0 <= m <= 190):
                outfile.write("Datele nu corespund restrictiilor impuse")
            else:
                for i in range(1, m + 1):
                    line = infile.readline().split()
                    if len(line) != 3:
                        outfile.write("Datele nu corespund restrictiilor impuse")
                        break

                    unu, doi, cost = line
                    cost = int(cost)
                    x = next(item[0] for item in codif if item[2] == unu)
                    y = next(item[0] for item in codif if item[2] == doi)
                    G[x].append((y, cost))
                    G[y].append((x, cost))

                unu, doi = infile.readline().split()
                start_node = next(item[0] for item in codif if item[2] == doi)

                def decodif(oras):
                    for x, y, s in codif:
                        if s == oras:
                            return x

                def costnod(nod):
                    for x, y, s in codif:
                        if nod == x:
                            return y

                def afisare(nod):
                    for x, y, s in codif:
                        if nod == x:
                            return s

                def bfs(nod):
                    t[nod] = nod
                    timp[nod] = costnod(nod)
                    q = Queue()
                    q.put(nod)

                    while not q.empty():
                        x = q.get()

                        for i, c in G[x]:
                            costnou = timp[x] + c + costnod(i)

                            if not timp[i] or costnou <= timp[i]:
                                timp[i] = costnou
                                t[i] = x
                                q.put(i)

                bfs(start_node)

                if timp[decodif(unu)] != 0:
                    outfile.write(str(timp[decodif(unu)]) + '\n')

                    plec = decodif(unu)
                    while plec != t[plec]:
                        outfile.write(afisare(plec) + '\n')
                        plec = t[plec]

                    outfile.write(afisare(decodif(doi)))
                else:
                    outfile.write("NU EXISTA TRASEU")

</syntaxhighlight>