LG#P2910. 航海之旅
航海之旅
题目描述
有 个岛屿,编号为 。从岛屿 直接航行到岛屿 的危险指数为 ,一次航行的总危险指数为沿途各段危险指数之和。
你从岛屿 出发,最终到达岛屿 。藏宝图要求行程中按顺序出现岛屿序列 ,保证 。这些指定岛屿不必在行程中相邻,岛屿和航线可以重复经过。
求满足藏宝图顺序要求的最小总危险指数。注意 不一定等于 ,中途允许经过其他指定岛屿,不会取消尚未按顺序完成的要求。
输入格式
第一行输入两个整数 $n,k\left(1\leqq n\leqq100;\ 2\leqq k\leqq10^4\right)$。
此后 行,第 行输入一个整数 。保证 。
再输入 行,每行 个整数 $d_{i,1},d_{i,2},\dots,d_{i,n}\left(0\leqq d_{i,j}\leqq10^5;\ d_{i,i}=0\right)$,代表有方向的危险指数。
输出格式
输出一个整数,代表最小总危险指数。
测试样例
3 4
1
2
1
3
0 5 1
5 0 2
1 2 0
7
样例 1 解释
可以依次经过 ,其中按顺序包含 。三段指定岛屿之间的最小费用分别为 ,总和为 。
2 3
1
1
2
0 7
2 0
7