from math import inf

G1_liste = [[(3,1)],[],[(0,4),(1,7),(5,2)],[(4,3)],[],[(3,1)],[(3,3)]]
G2_liste = [[(1,2),(3,1)],[(7,2)],[(5,-3),(4,1)],[],[(3,-2),(7,4),(5,-1)],[(1,1),(7,2)],[(1,-4)],[(6,8)]]

G1_mat = [[0,inf,inf,1,inf,inf,inf],
          [inf,0,inf,inf,inf,inf,inf],
          [4,7,0,inf,inf,2,inf],
          [inf,inf,inf,0,3,inf,inf],
          [inf,inf,inf,inf,0,inf,inf],
          [inf,inf,inf,1,inf,0,inf],
          [inf,inf,inf,3,inf,inf,0]]

G2_mat = [[0,2,inf,1,inf,inf,inf,inf],
          [inf,0,inf,inf,inf,inf,inf,2],
          [inf,inf,0,inf,1,-3,inf,inf],
          [inf,inf,inf,0,inf,inf,inf,inf],
          [inf,inf,inf,-2,0,-1,inf,4],
          [inf,1,inf,inf,inf,0,inf,2],
          [inf,-4,inf,inf,inf,inf,0,inf],
          [inf,inf,inf,inf,inf,inf,8,0]]

def poidsArc_liste(G,s,t):
    for couple in G[s]:
        (voisin,poids) = couple
        if voisin == t :
            return poids
    return inf

def poidsArc_mat(G,s,t):
    return G[s][t]

def poidsChemin_liste(G,c):
    n = len(c)
    out = 0
    for i in range(n-1):
        out += poidsArc_liste(G,c[i],c[i+1])
    return out

def poidsChemin_mat(G,c):
    n = len(c)
    out = 0
    for i in range(n-1):
        out += poidsArc_mat(G,c[i],c[i+1])
    return out

def estVide(l):
    for valeur in l :
        if valeur :
            return False
    return True

def minimum(l,d):
    indice = 0
    while not l[indice] :
        indice += 1
    for i in range(indice+1,len(d)):
        if l[i] and d[i]<d[indice]:
            indice = i
    return indice

def Dijkstra(G,s):
    n = len(G)
    d = [inf for i in range(n)]
    non_traite = [True for i in range(n)]
    d[s]=0
    while not estVide(non_traite) :
        sommet = minimum(non_traite,d)
        non_traite[sommet] = False
        for couple in G[sommet]:
            (voisin,poids)=couple
            if non_traite[voisin] and d[sommet]+poidsArc_liste(G,sommet,voisin) < d[voisin] :
                    d[voisin] = d[sommet]+poidsArc_liste(G,sommet,voisin)
    return d