该题第一个py代码AC

解题思路:

注意事项:最后一个用例是1到1需要特判一下，不特判的话输出是负值。一道简单的dijkstra板子题

参考代码:

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

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

st=[False]*(n+1)

gra=[[float('inf') for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):

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

    gra[u][v]=c+t[v]

    gra[v][u]=c+t[u]

def dijkstra():

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

    dis[1]=0

    for _ in range(n):

        t=-1

        for j in range(1,n+1):

            if st[j]==False and (t==-1 or dis[t]>dis[j]):

                t=j

        if t==n:break

        st[t]=True

        for j in range(1,n+1):

            dis[j]=min(dis[j],dis[t]+gra[t][j])

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

    else:return dis[n]

distance=dijkstra()

if n==1:

    print(0)

else:

    print(distance-t[n])