BZPRO

#2359. 商船运输

内存限制：128 MiB 时间限制：3 Sec
提交 提交记录 讨论

题目描述

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

输入格式

    第一行是是六个数N、M、port_num、good_num、ship_num、start，表示航海图的长、宽，以及港口总数、货物种类和船长拥有的船只数、所有船的初始位置(停泊的港口编号)。
    以下N+1行是一个N×M的矩阵，在矩阵中0、1、2分别对应海洋、港口和陆地。港口的编号对应由上至下，由左至右(由上至下优先)的读入顺序，第一个读入的港口编号为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个任务，每个任务占一行，包含两个数i、j，表示港口j需要货物i。
文件一行中相临两数用一个或多个空格隔开。
 

输出格式

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

样例

样例输入


			
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

样例输出


			
54

数据范围与提示

数据范围

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

BZPRO Powered by Remmina.
Github Repository