3107: 最短路径(dijkstra算法)

解题思路:

注意事项:

参考代码:

n = int(input())
v0 = int(input())-1
matrix = []
M = float("inf")
for i in range(n):
    matrix.append(list(input().split()))

for i in range(n):
    for j in range(n):
        if matrix[i][j] == "-":
            matrix[i][j] = M
        else:
            matrix[i][j] = int(matrix[i][j])

def dijkstra(matrix,v0):
    used_node = [False] * n
    distance = [M] * n
    distance[v0] = 0
    while used_node.count(False):
        min_value = M
        min_value_index = -1
        for i in range(n):
            if not used_node[i] and distance[i] < min_value:
                min_value = distance[i]
                min_value_index = i
        if min_value_index == -1:
            break
        used_node[min_value_index] = True
        for i in range(n):
            distance[i] = min(distance[i],distance[min_value_index]+matrix[min_value_index][i])
    return distance

distance = dijkstra(matrix,v0)
for i in range(0,n):
    if i == v0:
        continue
    print("("+str(v0+1)+" -> "+str(i+1)+") = "+str(distance[i]))