7-2 单源最短路径 分数 10 作者 朱允刚 单位 吉林大学 请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点，编号为0至n-1，以顶点0作为源点。 输入格式: 输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。 输出格式: 输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。 输入样例: 4 4 0 1 1 0 3 1 1 3 1 2 0 1 输出样例: 1 1 代码长度

下面是使用Dijkstra算法求解单源最短路径的Python代码实现，时间复杂度为O(ElogV)：

import heapq

INF = float('inf')

n, e = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

dist = [INF] * n
dist[0] = 0
visited = [False] * n
heap = [(0, 0)]

while heap:
    d, u = heapq.heappop(heap)
    if visited[u]:
        continue
    visited[u] = True
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(heap, (dist[v], v))

for i in range(1, n):
    if dist[i] == INF:
        print(-1, end=' ')
    else:
        print(dist[i], end=' ')

其中，dist数组表示源点0到各个顶点的最短路径长度，visited数组表示该顶点是否已经被访问过。heapq模块用于维护一个小根堆，每次取出堆顶的元素表示到某个顶点的最短路径已经确定。在更新每个顶点的最短路径时，如果发现新的路径比原来的路径更短，则更新dist数组并将该顶点加入小根堆中。