Editing 4064 - Ghiocel (section)

= Explicație =
Ghiocel locuiește în casa cu numărul <code>6</code>. Colegele lui stau în casele <code>1 4 8 10</code>. Până la casele <code>1</code> și <code>4</code> ajunge mergând pe un număr minim de străzi.

== Exemplul 2: ==
<code>ghiocelIN.txt</code>
 101 12 6
 1 2
 1 7
 1 10
 2 4
 2 5
 2 6
 3 4
 4 5
 5 6
 7 8
 8 10
 9 10
 4
 1 4 8 10
<code>ghiocelOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def check_constraints(n, m, edges):
    if not (1 <= n <= 100) or not (1 <= m <= n * (n - 1) / 2):
        return False

    for a, b in edges:
        if not (1 <= a <= n) or not (1 <= b <= n):
            return False

    return True

def BFS(start):
    q = deque([start])

    while q:
        current = q.popleft()

        for neighbor in vecini[current]:
            if not gasit[neighbor]:
                gasit[neighbor] = True
                q.append(neighbor)
                distanta[neighbor] = distanta[current] + 1

def main():
    global vecini, gasit, distanta
    with open("ghiocelIN.txt", "r") as file_in:
        n, m, start = map(int, file_in.readline().split())

        edges = [tuple(map(int, file_in.readline().split())) for _ in range(m)]

        if not check_constraints(n, m, edges):
            with open("ghiocelOUT.txt", "w") as file_out:
                file_out.write("Datele nu corespund restrictiilor impuse")
            return

        vecini = {i: set() for i in range(1, n + 1)}
        gasit = [False] * (n + 1)
        distanta = [0] * (n + 1)

        for a, b in edges:
            vecini[a].add(b)
            vecini[b].add(a)

        BFS(start)

        fete = int(file_in.readline())  # Read the number of girls from the file
        colege = set(map(int, file_in.readline().split()))

    with open("ghiocelOUT.txt", "w") as file_out:
        mini = float('inf')
        for i in colege:
            mini = min(mini, distanta[i])

        result = [i for i in colege if distanta[i] == mini]
        file_out.write(" ".join(map(str, result)))

if __name__ == "__main__":
    main()

</syntaxhighlight>