a star 2

import operator
from queue import PriorityQueue
inf=9999999999
graph = {'Oradea':{'Zerind':71,'Sibiu':151},'Zerind':{'Oradea':71,'Arad':75},'Arad':{'Zerind':75,'Timisoara':118,'Sibiu':140},'Timisoara':{'Arad':118,'Lugoj':111},'Lugoj':{'Timisoara':111,'Mehadia':70},'Mehadia':{'Lugoj':70,'Dobreta':70},'Dobreta':{'Mehadia':75,'Craiova':120},'Craiova':{'Dobreta':120,'Rimnicu Vilcea':146,'Pitesti':138},'Sibiu':{'Arad':140,'Oradea':151,'Rimnicu Vilcea':80,'Fagaras':99},'Rimnicu Vilcea':{'Sibiu':80,'Craiova':146,'Pitesti':97},'Fagaras':{'Sibiu':99,'Bucharest':221},'Pitesti':{'Bucharest':101,'Rimnicu Vilcea':97,'Craiova':138},'Bucharest':{'Fagaras':211,'Pitesti':101,'Giurgiu':90,'Urziceni':85},'Giurgiu':{'Bucharest':90},'Urziceni':{'Bucharest':85,'Hirsova':98,'Vaslui':142},'Hirsova':{'Urziceni':98,'Eforie':86},'Eforie':{'Hirsova':86},'Vaslui':{'Urziceni':142,'Iasi':92},'Iasi':{'Neamt':87,'Vaslui':92},'Neamt':{'Iasi':87}}
hsld = {'Arad':366, 'Bucharest':0, 'Craiova':160, 'Dobreta':242, 'Eforie':161, 'Fagaras':176, 'Giurgiu':77, 'Hirsova':151, 'Iasi':226, 'Lugoj':244, 'Mehadia':241, 'Neamt':234, 'Oradea':380, 'Pitesti':100, 'Rimnicu Vilcea':193, 'Sibiu':253, 'Timisoara':329, 'Urziceni':80, 'Vaslui':199, 'Zerind':374}
#d = {'Arad':inf, 'Bucharest':inf, 'Craiova':inf, 'Dobreta':inf, 'Eforie':inf, 'Fagaras':inf, 'Giurgiu':inf, 'Hirsova':inf, 'Iasi':inf, 'Lugoj':inf, 'Mehadia':inf, 'Neamt':inf, 'Oradea':inf, 'Pitesti':inf, 'Rimnicu Vilcea':inf, 'Sibiu':inf, 'Timisoara':inf, 'Urziceni':inf, 'Vaslui':inf, 'Zerind':inf}
par={}
d={}
for i in graph.keys():
    par[i]=i
    d[i]=inf
#print(par)
#print(type(d['Arad']))
start = 'Arad'
destination = 'Bucharest'
pq=PriorityQueue();
pq.put((-hsld[start],start))
path=[]
d[start]=0
cost=0
while not pq.empty():
    k=pq.get()
    val=k[0]
    node=k[1]
    for curnode in graph[node].keys():
        if curnode==par[node]:
            continue
        curval=graph[node][curnode]
        if (curval+d[node])<d[curnode]:
            d[curnode]=curval+d[node]
            par[curnode]=node
            pq.put((-hsld[curnode]-d[curnode],curnode))


node=destination
while node!=start:
    path.append(node)
    node=par[node]
path.append(start)
path.reverse()
print(path)
print(d[destination])