题解

题目描述
给定一个救援物资集结点（编号为 $0$ ）和 $N$ 个受灾乡镇（编号为 $1$ 到 $N$ ），以及它们之间的距离矩阵。矩阵大小为 $(N+1)\times(N+1)$ ，其中元素 $d_{ij}$ 表示节点 $i$ 到节点 $j$ 的距离，不相邻时为 $0$ 。现在要求从节点 $0$ 到指定乡镇节点 $m$ 的最短路径长度。

思路
典型的单源最短路问题，可用 Dijkstra 算法 解决，适用于所有边权非负的情况。