#971. [USACO08OPEN] Clear And Present Danger S

[USACO08OPEN] Clear And Present Danger S

题目描述

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

海上有 N(1≤N≤100)N(1\leq N\leq 100) 个岛屿,用 11 到 NN 编号。约翰从 11 号小岛出发,最后到达 NN 号小岛。

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

输入格式

第一行:两个用空格隔开的正整数 NN 和 MM。

第二到第 M+1M+1 行:第 i+1i+1 行用一个整数 AiA_i 表示 FJ 必须依次经过的第 ii 个岛屿。保证 A1=1,AM=NA_1=1,A_M=N。

第 M+2M+2 到第 N+M+1N+M+1 行:第 i+M+1i+M+1 行包含 NN 个用空格隔开的非负整数分别表示 ii 号小岛到第 1…N1\dots N 号小岛的航线各自的危险指数。保证第 ii 个数是 00。

输出格式

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

样例

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

题目来源:洛谷 P2910