题解

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

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

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

题目内容

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

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

输入描述

第一行，$N$，受灾乡镇个数,$3<=N<=20$

第二行至第$N+2$行，救援物质集结点以及各乡镇之间的货($N+1$个节点之间的相互距离短阵),距离取值范围是$[0,100]$、序号的节点表示救援物质集结点，序号$1-N$的节点表示各个受灾乡镇,$0$表示两个节点不相邻,

第$N+3$行，$m$，要抵达的乡镇序号(范围$1-N$)

输出描述

从物质集结点(节点$0$)到乡镇$m$(节点$m$)的最短路径长度

样例1

输入

5
0 5 13 0 0 0
5 0 12 0 75 0
13 12 0 25 0 0
0 0 25 0 35 20
0 75 0 35 0 40
0 0 0 20 40 0
3

输出

38

说明

从$0$到$3$的最短路径为$0-2-3$，长度为$13+25=38$

样例2

输入

5
0 5 13 0 0 0
5 0 12 0 75 0
13 12 0 25 0 0
0 0 25 0 35 20
0 75 0 35 0 40
0 0 0 20 40 0
5

输出

58

说明

从$0$到$5$的最短路径为$0-2-3-5$，长度为$13+25+20=58$