LG#P2910. 航海之旅

航海之旅

题目描述

\hspace{15pt}有 nn 个岛屿,编号为 1∼n1\sim n。从岛屿 ii 直接航行到岛屿 jj 的危险指数为 di,jd_{i,j},一次航行的总危险指数为沿途各段危险指数之和。

\hspace{15pt}你从岛屿 11 出发,最终到达岛屿 nn。藏宝图要求行程中按顺序出现岛屿序列 a1,a2,…,aka_1,a_2,\dots,a_k,保证 a1=1,ak=na_1=1,a_k=n。这些指定岛屿不必在行程中相邻,岛屿和航线可以重复经过。

\hspace{15pt}求满足藏宝图顺序要求的最小总危险指数。注意 di,jd_{i,j} 不一定等于 dj,id_{j,i},中途允许经过其他指定岛屿,不会取消尚未按顺序完成的要求。

输入格式

\hspace{15pt}第一行输入两个整数 $n,k\left(1\leqq n\leqq100;\ 2\leqq k\leqq10^4\right)$。

\hspace{15pt}此后 kk 行,第 ii 行输入一个整数 ai(1≦ai≦n)a_i\left(1\leqq a_i\leqq n\right)。保证 a1=1,ak=na_1=1,a_k=n。

\hspace{15pt}再输入 nn 行,每行 nn 个整数 $d_{i,1},d_{i,2},\dots,d_{i,n}\left(0\leqq d_{i,j}\leqq10^5;\ d_{i,i}=0\right)$,代表有方向的危险指数。

输出格式

\hspace{15pt}输出一个整数,代表最小总危险指数。

测试样例

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

样例 1 解释

\hspace{15pt}可以依次经过 1→3→2→3→1→31\to3\to2\to3\to1\to3,其中按顺序包含 1,2,1,31,2,1,3。三段指定岛屿之间的最小费用分别为 3,3,13,3,1,总和为 77。

2 3
1
1
2
0 7
2 0
7