p1396营救-最短路dijkstra

p1396营救-最短路dijkstra是一道经典最短路径问题，通常使用Dijkstra算法来解决。该问题描述如下：

给定一个n×m的矩阵，每个格子代表一个城市，其中的数字表示该城市的高度。现在有一支救援队需要从某个城市出发，到达另一个城市进行营救。救援队只能沿着上下左右四个方向移动，且只能从高度较低的城市移动到高度较高的城市。请问，救援队从起点城市到达终点城市的最短路径长度是多少？

解决这个问题的一种常用方法是使用Dijkstra算法。Dijkstra算法是一种贪心算法，用于求解单源最短路径问题。它的基本思想是从起点开始，逐步扩展到其他节点，每次选择当前距离起点最近的节点进行扩展，直到扩展到终点或者所有节点都被扩展完毕。

具体步骤如下：
1. 初始化距离数组dist，将起点的距离设为0，其他节点的距离设为无穷大。
2. 创建一个优先队列（最小堆），将起点加入队列。
3. 当队列不为空时，取出队列中距离起点最近的节点u。
4. 遍历节点u的所有邻居节点v，如果从起点到节点v的距离通过节点u更短，则更新节点v的距离，并将节点v加入队列。
5. 重复步骤3和步骤4，直到队列为空或者终点被扩展到。
6. 最终，终点的距离即为起点到终点的最短路径长度。