编程介的小学生 2019-03-21 13:12 采纳率: 20.5%
浏览 155

用邻接表实现距离数组的存储的计算,用C语言的程序编写的方法如何解决

Problem Description
Your Irish pizza and kebab restaurant is doing very well. Not only is the restaurant full almost every night, but there is also an ever increasing number of deliveries to be made, all over town. To meet this demand, you realize that it will be necessary to separate the delivery service from the restaurant. A new large kitchen, only for baking pizzas and being a base for deliveries, has to be established somewhere in town. The main cost in the delivery service is not the making of the pizza itself, but the time it takes to deliver it. To minimize this, you need to carefully plan the location of the new kitchen. To your help you have a database of all last year's deliveries. For each block in the city, you know how many deliveries were made there last year. The kitchen location will be chosen based on the assumption that the pattern of demand will be the same in the future.
Your city has a typical suburban layot – an orthogonal grid of equalsize square blocks. All places of interest (delivery points and the kitchen) are considered to be located at street crossings. The distance between two street crossings is the Manhattan distance, i.e., the number of blocks you have to drive vertically, plus the number of blocks you have to drive horizontally. The total cost for a delivery point is its Manhattan distance from the kitchen, times the number of deliveries to the point. Note that we are only counting the distance from the kitchen to the delivery point.
Even though we always drive directly back to the kitchen after a delivery is made, this (equal) distance is not included in the cost measure.

Input
On the rst line, there is a number, 1 <=n <=20, indicating the number of
test cases. Each test case begins with a line with two integers, 1 <= x <= 100, 1<= y <= 100, indicating the size of the two-dimenstional street grid. Then follow y lines, each with x integers, 0<= d <=1000, indicating the number of deliveries made to each street crossing last year.

Output
For each test case, output the least possible total delivery cost (the sum of all delivery costs last year), assuming that the kitchen was located optimally.There should be one line for each test case, with an integer indicating the cost, followed by a single space and the word 'blocks'.

Sample Input
2
4 4
0 8 2 0
1 4 5 0
0 1 0 1
3 9 2 0
6 7
0 0 0 0 0 0
0 1 0 3 0 1
2 9 1 2 1 2
8 7 1 3 4 3
1 0 2 2 7 7
0 1 0 0 1 0
0 0 0 0 0 0

Sample Output
55 blocks
162 blocks

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 Arcgis相交分析无法绘制一个或多个图形
    • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
    • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
    • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
    • ¥30 3天&7天&&15天&销量如何统计同一行
    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)