题目描述

kAc公司为它在各地的用户提供服务。公司有三名员工。如果某处有人寻求服务且当前那里没有任何员工,就会有一位员工从当前所在地赶到寻求服务的地点。任何时刻,最多只能有一个人移动。员工只会因为提供服务而易懂,且同一时刻不可以有多个人在同一地点。从p处移动到q处需要的费用是C(p,q)。注意,C(p,q)不一定等于C(q,p),但是停留在远地不需要费用,即C(p,p)=0。公司提供的服务必须满足先请求-先满足的原则,按照请求服务的顺序提供服务。你的任务是找到一个服务方法,使得服务的总费用最小。

对于20%:L<=10

对于40%:L<=50

对于80%:L<=100

对于100%:3<=L<=200,1<=N<=1000,所有给定的费用不超过2000。

输入格式

输入文件第一行包含两个整数L和N。L表示地点的数量。N表示寻求服务的数量。地点的标号为1到L。接下来L行,每行包含L个非负整数,第i+1行第j个数表示C(i,j)。

最后一行包含N个整数,表示询问。初始时,员工1位于地点1、员工2位于地点2、员工3位于地点3。

输出格式

包含一个整数M,表示你求出的最小总费用。

样例输入
样例输出
注释

对于20%:L<=10

对于40%:L<=50

对于80%:L<=100

对于100%:3<=L<=200,1<=N<=1000,所有给定的费用不超过2000。

提交题目 Error [ 更改语言 ] Language
C C++ Pascal
相关讨论
查看更多讨论
发布新讨论 讨论