1148.py

# Algoritmo de Dijkstra

import heapq

n = 1
m = 1

while(n != 0 and m != 0):
    n, m = input().split()              # ler numero de vertices e arestas
    n = int(n)
    m = int(m)

    n_out = [[] * n for i in range(n)]  # definir listas de adjacencia
    custo = []                          # definir a matriz de custos (pesos)
    for i in range(n):
        linha = []
        for j in range(n):
            if i == j:
                linha.append(0)
            else:
                linha.append(-1)
        custo.append(linha)

    # custo = [ [0, -1, -1], [-1, 0, -1], [-1, -1 , 0] ]
    # n_out = [ [], [], [] ]

    for j in range(m):                  # ler as m arestas do digrafo
        a,b,H = input().split()         # ler aresta de a para b com custo H
        a = int(a) - 1
        b = int(b) - 1
        H = int(H)
        n_out[a].append(b)              # b é vizinho de saída de a
        custo[a][b] = H

    #receber o numero de consultas:
    n_cons = input()
    n_cons = int(n_cons)
    consultas = []
    for i in range(n_cons):
        cidade1, cidade2 = input().split()
        consultas.append([int(cidade1) - 1, int(cidade2) - 1])

    #inicializacoes

    print("n_out: " + str(n_out))
    print("custo: " + str(custo))
    print("infinity: " + str(9999999))
    print("n_cons: " + str(n_cons))
    print("consultas: " + str(consultas)) 

    # L guarda os valores dos custos dos menores caminhos.

    marca = n*[0]
    L = n*[9999999]

    for consulta in consultas:
        v = consulta[0]
        L[v] = 0                            # 0 será a raiz do algoritmo
        HEAP = [(0,v)]                         # cada posição do heap guarda (L(w), w)

        for w in range(n):
            if(w != v):
                heapq.heappush(HEAP,(L[w],w))      # iniciar o heap com todos os valores
        pai = n*[-1]

        # print("n_out: " + str(n_out))
        # print("custo: " + str(custo))
        # print("infinity: " + str(9999999))
        # print("n_cons: " + str(n_cons))
        # print("consultas: " + str(consultas))
        # print("HEAP: " + str(HEAP))

        while HEAP != []:
            Hmin, v = heapq.heappop(HEAP)      # tirar a raiz do heap
            marca[v] = 1
            for w in n_out[v]:
                if marca[w] == 0: # Se não foi visitado
                    if L[v] + custo[v][w] < L[w]: # Objetivo: min(L[v] + custo[v][w], L[w])
                        # achar posicao de w no heap:
                        for i in range(len(HEAP)):
                            if HEAP[i] == (L[w],w):
                                pos = i
                                break
                        L[w] = L[v] + custo[v][w]    # atualizar o valor de L[w]
                        HEAP[pos] = (L[w],w)
                        heapq._siftdown(HEAP,0,pos)     # atualizar o heap
                        pai[w] = v
        print("----inicio----")
        print(consulta)
        print(L)
        print(L[consulta[1]])
        print("----fim----")
    # print(pai)