Open ManuShi98 opened 1 year ago
https://manushi98.github.io/2017/10/13/POJ%20%E2%80%93%202387%20Til%20the%20Cows%20Come%20Home%EF%BC%88Dijkstra%E5%A0%86%E4%BC%98%E5%8C%96%EF%BC%89/
思路：最短路的裸题，不过想尝试一下以前没用过的Dijkstra的堆优化。Dijkstra的思路简单的说就是找目前没有扫描过的，且到出发点最近的点。标记其为使用过后再更新其周围的点的最短路径。常规时间复杂度为O(|V|^2)。在算法中我们可以使用一个小顶堆维护当前的离出发点最近的点，避免了多余的扫描，使得复杂度变为O(|E|log|V|)。这题一眼扫过去是个裸题就直接做了，没看到题目说可以有重边。。
https://manushi98.github.io/2017/10/13/POJ%20%E2%80%93%202387%20Til%20the%20Cows%20Come%20Home%EF%BC%88Dijkstra%E5%A0%86%E4%BC%98%E5%8C%96%EF%BC%89/
思路：最短路的裸题，不过想尝试一下以前没用过的Dijkstra的堆优化。Dijkstra的思路简单的说就是找目前没有扫描过的，且到出发点最近的点。标记其为使用过后再更新其周围的点的最短路径。常规时间复杂度为O(|V|^2)。在算法中我们可以使用一个小顶堆维护当前的离出发点最近的点，避免了多余的扫描，使得复杂度变为O(|E|log|V|)。这题一眼扫过去是个裸题就直接做了，没看到题目说可以有重边。。