题解
题目描述
给定一个救援物资集结点（编号为 0）和 N 个受灾乡镇（编号为 1 到 N），以及它们之间的距离矩阵。矩阵大小为 (N+1)×(N+1)，其中元素 dij 表示节点 i 到节点 j 的距离，不相邻时为 0。现在要求从节点 0 到指定乡镇节点 m 的最短路径长度。
思路
典型的单源最短路问题，可用 Dijkstra 算法 解决，适用于所有边权非负的情况。
- 用数组 dist[] 记录从源点 0 到各节点的最短距离，初始时
题目内容
某市发生地震后，需要将救援物资从唯一的救援物资集结点送往受灾乡镇。应急部门通过无人机对受灾地区地形进行了勘察，获得了各乡镇之间以及各乡镇到集结点之间的距离数据。
设所有地点共有 N+1 个，其中集结点编号为 0，受灾乡镇编号为 1 到 N。这些地点之间的距离以矩阵形式给出。矩阵第 i 行第 j 列的值表示地点 i 到地点 j 的直达距离；值为 0 表示两个地点不相邻。
请计算从救援物资集结点 0 到编号为 m 的受灾乡镇的最短路径长度。
约束条件：
- 受灾乡镇个数 N 满足 3≤N≤20。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
