传送门:牛客

题目描述

农夫约翰正驾驶一条小艇在牛勒比海上航行．
海上有 N(1≤N≤100)N(1\leq N\leq 100)N(1≤N≤100) 个岛屿，用 111 到 NNN 编号．约翰从 111 号小岛出发，最后到达 NNN 号小岛．
一张藏宝图上说，如果他的路程上经过的小岛依次出现了 A1,A2,…,AM(2≤M≤10000)A_1,A_2,\dots ,A_M(2\leq M\leq 10000)A1​,A2​,…,AM​(2≤M≤10000) 这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数 Di,j(0≤Di,j≤100000)D_{i,j}(0\leq D_{i,j}\leq 100000)Di,j​(0≤Di,j​≤100000) 来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

输入:
3 4 
1 
2 
1 
3 
0 5 1 
5 0 2 
1 2 0 
输出:
7

一道简单的多源最短路的题目.N并不是很大,所以使用DloydDloydDloyd来解决这道题

对于floydfloydfloyd网上有大量的博客和题解,不乏讲的很清楚的(肯定比我讲的要清楚),所以此处就不再赘述了

提醒一下:学完之后可以考虑一下为什么floydfloydfloyd的中间点循环需要放在最外面而不能是最里面,这可以增加对floydfloydfloyd算法的理解!

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include