1825 - Zoomba

Enunț

În țara Zoomba trăiesc K prieteni, fiecare în localități diferite. În această țară se găsesc N orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei K prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă 1 litru de benzină.

Cerința

Știind că odată ce au ajuns în același oraș 2 sau mai mulți prieteni, aceștia iși pot continua drumul cu o singură mașină, să se determine consumul minim de benzină pentru ca aceștia să ajungă în orașul Z.

Date de intrare

Fișierul de intrare zoombaIN.txt conține pe prima linie numerele N, M(numărul de șosele), K și Z. Pe următoarea linie se află K numere, reprezentând pozițiile inițiale ale celor K prieteni. Pe următoarele M linii se află câte o pereche i j, cu semnificația că există șosea de la orașul i la orașul j.

Date de ieșire

Fișierul de ieșire zoombaOUt.txt va conține pe prima linie numărul C, ce va fi egal cu consumul minim de combustibil necesar ca cei K prieteni să se întâlnească în orașul Z, sau -1 în cazul în care aceștia nu pot ajunge în el.Î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 ≤ Z ≤ N ≤ 200
• 1 ≤ K ≤ min(N,10)

Exemplul 1:

zoombaIN.txt

5 4 3 5
1 2 3
1 4
2 4
3 4
4 5

zoombaOUt.txt

4

Exemplul 2:

zoombaIN.txt

201 4 3 5
1 2 3
1 4
2 4
3 4
4 5

zoombaOUt.txt

Datele nu corespund restrictiilor impuse

Rezolvare

from collections import deque
import sys

def check_constraints(n, k, z):
    if not (1 <= z <= n <= 200 and 1 <= k <= min(n, 10)):
        with open('zoombaOUT.txt', 'w') as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        sys.exit()

def main():
    kmax = 10
    nmax = 203
    inf = int(1e9)

    def lee(v):
        while coada:
            k = coada.popleft()
            for i in range(len(g[k])):
                if dp[g[k][i]][v] > dp[k][v] + 1:
                    dp[g[k][i]][v] = dp[k][v] + 1
                    coada.append(g[k][i])

    def construct(l):
        ret = 0
        i = 0
        while l:
            ret ^= (1 << i)
            i += 1
            l -= 1
        return ret

    def nbiti(x):
        k = 0
        while x:
            k += (x & 1)
            x >>= 1
        return k

    # Redirect input and output to files
    sys.stdin = open('zoombaIN.txt', 'r')
    sys.stdout = open('zoombaOUT.txt', 'w')

    n, m, k, z = map(int, input().split())

    # Check constraints and exit if not met
    check_constraints(n, k, z)

    a = list(map(int, input().split()))
    g = [[] for _ in range(nmax)]
    dp = [[inf] * (1 << (kmax + 1)) for _ in range(nmax)]
    coada = deque()

    for _ in range(m):
        i, j = map(int, input().split())
        g[i].append(j)
        g[j].append(i)

    for i in range(k):
        dp[a[i]][1 << i] = 0
        coada.append(a[i])
        lee(1 << i)

    for l in range(2, k + 1):
        for j in range(construct(l), (1 << k)):
            if nbiti(j) == l:
                for i in range(1, n + 1):
                    for c in range(1, j):
                        if (j | c) == j:
                            dp[i][j] = min(dp[i][j], dp[i][c] + dp[i][j ^ c])
                    coada.append(i)
                lee(j)

    result = dp[z][(1 << k) - 1] if dp[z][(1 << k) - 1] != inf else -1
    print(result)

    # Close the files
    sys.stdin.close()
    sys.stdout.close()

if __name__ == "__main__":
    main()