题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

Dijkstra + 二叉堆 （复杂度O(VlgV+ElgV)）

邻接表存储边，维护一个最小堆（堆中为(到节点1的距离，节点)的元祖）。每次取堆中的最小值。

python代码

from queue import PriorityQueue
import sys

temp = sys.stdin.readline().split()
n, m = int(temp[0]), int(temp[1])
edge = [{} for _ in range(n+1)]
for _ in range(m):
    temp = sys.stdin.readline().split()
    x, y, z = int(temp[0]), int(temp[1]), int(temp[2])
    if y not in edge[x] or edge[x][y] > z:
        edge[x][y] = z

d = [sys.maxsize for _ in range(n+1)]
q = PriorityQueue()
q.put((0, 1))
while not q.empty():
    dis, node = q.get()
    if dis > d[node]:
        continue
    for key, val in edge[node].items():
        if d[key] > val + dis:
            d[key] = val + dis
            q.put((d[key], key))

print(d[n] if d[n]!=sys.maxsize else -1)

时间复杂度分析

耗时主要有两个方面，一个是取最小值（代码中的q.get()）；一个是往最小堆中更新的操作（代码中的q.put()）。设图的节点有V个，边有E条。

第一部分，由于我们实际上每次while循环是在取未访问集合中的一个点，所以while循环共进行V次，从最小堆中取元素的复杂度为O(lgV)，故第一部分复杂度为O(VlgV)。

第二部分，事实上q.put()操作是在访问边的时候才可能执行，而for key, val in edge[node].items(): ..这个循环使得每条边只访问一次，故最多访问E次，每次复杂度为O(lgV)。第二部分复杂度为O(ElgV)。

故总的时间复杂为O(VlgV+ElgV)。