我又来了！堆优化版py代码（AC蓝桥官网）题目数据有点问题

解题思路:

注意事项:应该是有一个数据在输入u，v，c的时候少了一项，所以报错

参考代码:

import heapq

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

t=[0]+list(map(int,input().split()))

N=20010

#链式星向前

e=[0]*N#指向的点

w=[0]*N#权值

ne=[0]*N#同起点下的上一条边的编号

h=[-1]*N#同起点下最后一条边的编号

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

index=0#编号

st=[False]*(n+1)

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[1]=0

    heap=[]

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

    while heap:

        t=heapq.heappop(heap)

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

        if st[vertex]:

            continue

        st[vertex]=True

        i=h[vertex]#从vertex集合里的最后一条边开始找

        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]#vertex集合里的倒数第二条边，也就是上一条边

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

    else:return dis[n]

for _ in range(m):

    u,v,c=map(int,input().split())

    add(u,v,c+t[v])

    add(v,u,c+t[u])

if n==1:

    print(0)

else:

    print(dijkstra()-t[n])