#P2910. [USACO08OPEN] 迫在眉睫的危机
[USACO08OPEN] 迫在眉睫的危机
题目描述
农夫约翰正驾驶一条小艇在牛勒比海上航行。海上有 个岛屿,用 到 编号.约翰从 号小岛出发,最后到达 号小岛。
一张藏宝图上说,如果他的路程上经过的小岛依次出现了 这样的序列(不一定相邻),那他最终就能找到古老的宝藏. 但是,由于牛勒比海有海盗出没.约翰知道任意两个岛屿之间的航线上海盗出没的概率,他用一个危险指数 来描述.他希望他的寻宝活动经过的航线危险指数之和最小.那么,在找到宝藏的前提下,这个最小的危险指数是多少呢?
输入格式:
第一行:两个用空格隔开的正整数 和 。
第二到第 行:第 行用一个整数 表示 FJ 必须经过的第 个岛屿
第 到第 行:第 行包含 个用空格隔开的非负整数分别表示 号小岛到第 号小岛的航线各自的危险指数。保证第 个数是 。
输出格式
第一行:FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。
3 4
1
2
1
3
0 5 1
5 0 2
1 2 0
7