[Usaco2008 Open] Clear And Present Danger 寻宝之路

农夫约翰正驾驶一条小艇在牛勒比海上航行。

海上有 $N$ 个岛屿，编号为 $1$ 到 $N$ 。约翰从 $1$ 号岛屿出发，最后到达 $N$ 号岛屿。一张藏宝图给出了长度为 $M$ 的岛屿序列 $A_1,A_2,\ldots,A_M$ ，其中 $1\le A_i\le N$ 、 $A_1=1$ 且 $A_M=N$ 。

如果约翰的航行路线中按顺序出现了该序列中的所有岛屿，且不要求这些岛屿在路线中相邻，他就能找到宝藏。

但是，牛勒比海有海盗出没。约翰知道从 $i$ 号岛屿到 $j$ 号岛屿的航线上发生危险的概率，并用危险指数 $D_{ij}$ （ $0\le D_{ij}\le 100000$ ）来描述这条航线的危险程度。他希望寻宝过程中经过的所有航线的危险指数之和最小。

请你求出在能够找到宝藏的前提下，最小的危险指数之和。

输入格式

第 $1$ 行输入 $N$ 和 $M$ 。

接下来 $M$ 行，每行输入一个整数，表示岛屿序列 $A$ 中的一个元素。保证 $1\le A_i\le N$ 、 $A_1=1$ 且 $A_M=N$ 。

接下来输入一个 $N\times N$ 的方阵，表示任意两个岛屿之间航线的危险指数。数据保证 $D_{ii}=0$ ；对于 $i\ne j$ ， $D_{ij}$ 与 $D_{ji}$ 可以不同。

输出最小的危险指数之和。

一种找到宝藏且危险指数之和为 $7$ 的航行路线是：

1\to 3\to 2\to 3\to 1\to 3。

其中，藏宝图要求的序列 $1,2,1,3$ 按顺序出现在该路线中。该路线避开了危险指数较大的 $1$ 号岛屿到 $2$ 号岛屿之间的航线。

本题为 USACO 2008 Open 试题「寻宝之路」，题面与测试数据整理自 BZOJ。