城市路(Dijkstra)

解题思路:

注意事项:

参考代码:

import heapq

N=100010

e=[0]*N

ne=[0]*N

w=[0]*N

h=[-1]*N

index=0

st=[False]*N

def add(a,b,c):

    global index

    e[index]=b

    w[index]=c

    ne[index]=h[a]

    h[a]=index

    index+=1

def dijkstra():

    dis=[float('inf')]*(n+1)

    dis[1]=0

    heap=[]

    heapq.heappush(heap,(dis[1],1))

    while heap:

        t=heapq.heappop(heap)

        distance,ver=t[0],t[1]

        if st[ver]==True:

            continue

        st[ver]=True

        i=h[ver]

        while i!=-1:

            j=e[i]

            if dis[j]>distance+w[i]:

                dis[j]=distance+w[i]

                heapq.heappush(heap,(dis[j],j))

            i=ne[i]

    if dis[n]==float('inf'): return -1

    else:return dis[n]

n,m=map(int,input().split())        

for i in range(m):

    a,b,c=map(int,input().split())

    add(a,b,c)

    add(b,a,c)

print(dijkstra())