危险降临 / 【模板】多源最短路(Floyd)

危险降临 / 【模板】多源最短路(Floyd)

出题人太菜,暂无测试数据。

[USACO08OPEN] Clear And Present Danger S

形式化题面

给定一张\(n\)个点的图和图中每两个节点之间的边权,以及一个\(m\)个点的序列。求该序列中相邻的点的最短路径之和。

题面翻译

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

输入输出格式

输入格式:

第一行:两个用空格隔开的正整数 \(N\) 和 \(M\)。
第二到第 \(M+1\) 行:第 \(i+1\) 行用一个整数 \(A_i\) 表示 FJ 必须经过的第 \(i\) 个岛屿
第 \(M+2\) 到第 \(N+M+1\) 行:第 \(i+M+1\) 行包含 \(N\) 个用空格隔开的非负整数分别表示 \(i\) 号小岛到第 \(1\dots N\) 号小岛的航线各自的危险指数。保证第 \(i\) 个数是 \(0\)。

输出格式

第一行:FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。

样例 #1

样例输入 #1

3 4 
1 
2 
1 
3 
0 5 1 
5 0 2 
1 2 0

样例输出 #1

7

说明

这组数据中有三个岛屿,藏宝图要求 FJ 按顺序经过四个岛屿:\(1\) 号岛屿、\(2\) 号岛屿、回到 \(1\) 号岛屿、最后到 \(3\) 号岛屿。每条航线的危险指数也给出了:航路\((1,2),(2,3),(3,1)\) 和它们的反向路径的危险指数分别是 \(5,2,1\)。

FJ 可以通过依次经过 \(1,3,2,3,1,3\) 号岛屿以 \(7\) 的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求 \((1,2,1,3)\)。我们避开了 \(1\) 号和 \(2\) 号岛屿之间的航线,因为它的危险指数太大了。

注意:测试数据中 \(a\) 到 \(b\) 的危险指数不一定等于 \(b\) 到 \(a\) 的危险指数!

信息

ID
1027
难度
1
分类
图结构 | 最短路 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者

相关

在下列训练计划中:

模板 | Templates