4064 - Ghiocel

Cerința

Într-un oraș sunt n case numerotate de la 1 la n. Între anumite case sunt străzi bidirecționale. În casa cu numărul g locuiește Ghiocel. El are k colege ale căror numere de casă îi sunt cunoscute și Ghiocel dorește să le ducă ghiocei la inceputul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei colegei sau colegelor care stă (stau) la o casă până la care Ghiocel are de parcurs un număr minim de străzi. Ajutați-l pe Ghiocel să determine numerele acestor case.

Date de intrare

Fișierul de intrare ghiocelIN.txt conține pe prima linie numerele n m g, reprezentând numărul de case, numărul de străzi și numărul casei în care locuiește Ghiocel. Urmează m linii cu câte două numere i j, cu semnificația: casele i și j sunt legate printr-o stradă bidirecțională. Pe următoarea linie se află numărul k a colegelor lui Ghiocel, iar pe ultima linie se află k numere distincte cuprinse între 1 și n, reprezentând numerele caselor unde locuiesc colegele lui Ghiocel.

Date de ieșire

Fișierul de ieșire ghiocelOUT.txt va conține pe prima linie numerele caselor unde locuiesc colege de-ale lui Ghicel până la care acesta are de parcurs un număr minim de străzi. Numerele se vor afișa în ordine crescătoare și separate prin câte un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ n * (n - 1) / 2
• 1 ≤ i, j ≤ n
• 1 ≤ k ≤ n

Exemplul 1:

ghiocelIN.txt

10 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

ghiocelOUT.txt

1 4

Explicație

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

Exemplul 2:

ghiocelIN.txt

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

ghiocelOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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