朴素dijkstra有两重循环,时间复杂度为O(n^2)。 因为内层循环有一个找最小距离的结点的操作,因此可以用堆来优化
堆取最小值O(1),调整堆O(logn),最多有m条边,因此堆优化的dijkstra复杂度为O(mlogn)
只需把dist有更新的结点入堆,因可能存在同一结点重复入堆的情况,设置一st[N]数组记录入堆的结点,若已被计算则continue。