UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2359. 商船运输

统计 下载数据

Description

开辟新航路以后,欧洲的海上贸易日益繁荣,许多商人带领着他们的船队,在世界各地来往穿梭。这其中有位很有头脑的XX船长,他十分重视收集各港口的供需情报,并以此确定他的下一步计划,通过减少运输的时间来获取更多的利益。他的情报包括以下的内容:
1.           一幅完整的航海图。这其中包含了陆地、海洋以及各港口的位置。船只每次只能沿上下左右四个方向移动一格(不可移到陆地上和地图外,可移进港口),且每次移动都需航行一天。
2.           各港口可供应的货物。当然,每种货物不可能到处都买的到,否则就用不着船队了。因此,规定每种货物最多只有20个的港口供应。
3.           各港口需要的货物。与情报2不同的是,各港所需的货物是变化的,即XX船长是逐渐得到新情报的。同时,每当他得到一个新的货物需求(i,j)(表示港口j需要货物i),他必须马上作出决策:选择几号船完成此任务。因为要计算出怎样最优是比较困难的,所以船长采取了这样一个近似的方法:找出“完成新任务所需时间”最少的船,将其用来完成新任务,若有多艘这样的船,则从中选择编号最小的。(“完成新任务所需时间”包含两个过程:航行到一个供应货物i的港口并上货和将货物i运到港口j并卸货,其中上货和卸货的时间忽略不计。因为上货港口的选择不同,所需的时间也会不同,所以,必须对上货的港口进行选择,使该船的“完成新任务所需时间”尽量短)
XX船长想要知道的是:他的所有船只共需多少时间来完成这些任务,即所有船只完成各自任务的时间和。
 

Input

    第一行是是六个数NMport_numgood_numship_numstart,表示航海图的长、宽,以及港口总数、货物种类和船长拥有的船只数、所有船的初始位置(停泊的港口编号)
    以下N+1行是一个N×M的矩阵,在矩阵中012分别对应海洋、港口和陆地。港口的编号对应由上至下,由左至右(由上至下优先)的读入顺序,第一个读入的港口编号为1,第二个读入的港口编号为2……
    N+2行到第N+port_num+1行按编号顺序给出了各港口供应的货物,其格式为:
       N1 p11  p12  … p1N1
       N2 p21  p22  … p2N2
       … … … … …
   Ni pi1  pi2  … piNi
       … … … … …
 Nport_num pport_num1 pport_num2 … pport_numNport_num
       Ni是港口i供应的货物总数,pij是港口i供应的第j种货物编号。
     N+port_num+2行是一个数Total,表示情报3中获得的任务总数,以下Total行按情报获得的时间给出了Total个任务,每个任务占一行,包含两个数ij,表示港口j需要货物i
文件一行中相临两数用一个或多个空格隔开。
 

Output

 仅有一个数T,是你的程序得出的所有船只完成各自任务的时间和。

Sample Input

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

Sample Output

54

Hint

数据范围

       1≤N、M≤100,1≤port_num≤100,1≤good_num

Source