【Python】L2-001 紧急救援 (25 分) — Dijkstra

import heapq
n,m,s,g=map(int,input().split())
x=list(map(int,input().split()))
ds=[0]*n#到达点 i 时的最大救援人数
#字典这种方式比较适合于有向边存在权重的情况
graph = [dict() for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a][b] =c
    graph[b][a] =c
#print(graph)

def init_distance(graph,s):
    distance={s:0}
    for vertex in range(n):
        if vertex!=s:
            distance[vertex]=float('inf')
    return distance

def dijkstra(graph,s):
    pqueue=[]
    heapq.heappush(pqueue,(0,s))#（0，s）0：起点（传入函数的s）到达目的地s的距离；s：目的地（第一次为s到s故距离是0）
    seen=set()#标记已走的地点
    parent={s:None}#key：当前地点，value：当前地点的前驱（第一次为s无前驱，故value是None）
    distance =init_distance(graph,s)# 初始化distance
    ds[s]=x[s]

    while len(pqueue)>0:
        pair=heapq.heappop(pqueue)#弹出parent优先级最高的（值越小），第一次是（0,s）
        dist=pair[0]#取出距离
        vertex=pair[1]#取出当前当前地点的名称
        seen.add(vertex) #将当前地点标记为已读
        node=graph[vertex].keys()#取出当前地点可以到达的所有地点名称

        for w in node:
            if w not in seen:#如果该地点没有被标记为已读
                if dist +graph[vertex][w]ds[w]:
                        heapq.heappush(pqueue, (dist + graph[vertex][w], w))  # 存在则更新
                        parent[w] = vertex  # 更新prent中到w的上一个地点为vertex
                        distance[w] = dist + graph[vertex][w]  # 跟新起点到w的最短距离
                        ds[w] = ds[vertex] + x[w]
    return parent,distance
parent,distance=dijkstra(graph,s)
#print(parent)
#print(distance)

#print(distance[g])#s到g的最短距离

cnt=0
l=[]#返回最短路径
#print(ds[g])
gx=g
while(gx!=None):
    l.append(gx)
    a=parent[gx]
    gx=a
    cnt+=1
l=l[::-1]
print(cnt-1,ds[g])
print(*l)
#print(ds)

只有14分emmmm