islands

from zad1testy import runtests
from copy import copy
from math import inf


def BFS(G, start,finish):
    from queue import Queue

    n = len(G)
    visited = [0 for i in range(n)]
    distance=[inf for i in range(n)]
    parent=[-1 for i in range(n)]

    distance[start]=0
    #parent[start]=start

    q = Queue()
    q.put([start,0,start])

    while not q.empty():
        u,weight,comingfrom = q.get()

        if weight>0:
            if visited[u]==0:
                q.put([u,weight-1,comingfrom])
        else:
            visited[u]=1
            parent[u]=comingfrom
            distance[u]=distance[comingfrom]+G[comingfrom][u]

            for i in range(n):
                if G[u][i]!=None and visited[i] == 0:
                    q.put([i,G[u][i],u])
            visited[u] = 2
    #return distance
    return min(distance[finish],distance[n//3+finish],distance[2*(n//3)+finish])

def islands(G, A, B):
    # tu prosze wpisac wlasna implementacje
    n=len(G)
    #podział każdego wierzchołka na 3
    #i dodatkowo wierzchołek [3*n] ma krawędzie o wadze 0 do różnych startów
    Graph=[[None for i in range(3*n+1)] for j in range(3*n+1)]
    # 0<= k <=n-1
    #0*n +k - przybyłem na wyspę mostem
    #1*n +k - przybyłem na wyspę promem
    #2*n +k - przybyłem na wyspę samolotem
    for i in range(n):
        for j in range(n):
            x=G[i][j]

            if x==1:
                Graph[n+i][j]=x
                Graph[2*n+i][j]=x
            elif x==5:
                Graph[i][n+j]=x
                Graph[2*n+i][n+j]=x
            elif x==8:
                Graph[i][2*n+j]=x
                Graph[n+i][2*n+j]=x
    #ze startu możemy iść gdziekolwiek
    Graph[3*n][A]=0
    Graph[3*n][n+A]=0
    Graph[3*n][2*n+A]=0
    Graph[3*n][3*n]=0 #potrzebne do poprawnego działania
    """
    for i in range(3*n):
        x=G[A][i%n]
        Graph[A][i]=x
        Graph[n+A][i]=x
        Graph[2*n+A][i]=x
    """ #^ stary pomysł
    res=BFS(Graph, 3*n,B)
    #print(res[0:n])
    #print(res[n:2*n])
    #print(res[2*n:3*n])
    if res<inf:
        return res
    else:
        return None




runtests( islands )