题目内容

某市发生地震，为了尽快将救援物质输送到受灾乡镇，需要你设计出从救援物质集结点(有仅有一个)到某一个受灾乡镇的最短线路

应急部门通过无人机助察了受灾地区地形，提供了各乡镇之间以及乡镇到救援物质集结点的距离，请你算出救援物质集结点到受灾多镇的最短路径。

题解

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

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

1. 用数组 $\mathrm{dist}[\,]$ 记录从源点 $0$ 到各节点的最短距离，初始时