Editing 1825 - Zoomba

= Enunț =
În țara Zoomba trăiesc <code>K</code> prieteni, fiecare în localități diferite. În această țară se găsesc <code>N</code> orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei <code>K</code> 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ă <code>1</code> litru de benzină.

= Cerința =
Știind că odată ce au ajuns în același oraș <code>2</code> 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 <code>Z</code>.

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

= Date de ieșire =
Fișierul de ieșire <code>zoombaOUt.txt</code> va conține pe prima linie numărul <code>C</code>, ce va fi egal cu consumul minim de combustibil necesar ca cei <code>K</code> prieteni să se întâlnească în orașul <code>Z</code>, sau <code>-1</code> î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 =

* <code>1 ≤ Z ≤ N ≤ 200</code>
* <code>1 ≤ K ≤ min(N,10)</code>

= Exemplul 1: =
<code>zoombaIN.txt</code>
 5 4 3 5
 1 2 3
 1 4
 2 4
 3 4
 4 5
<code>zoombaOUt.txt</code>
 4

= Exemplul 2: =
<code>zoombaIN.txt</code>
 201 4 3 5
 1 2 3
 1 4
 2 4
 3 4
 4 5
<code>zoombaOUt.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>