广度优先算法遍历一个数据结构里面的图相关的算法运用C语言的实现

Problem Description
Back to year 3024, humans finally developed a new technology that enables them to conquer the alien races. The new technology made it possible to produce huge spaceships known as Saber Tooth spaceships as powerful as the aliens' defending mammoths. At that time, humans ruled several planets while some others were under control of the aliens. Using Saber Tooth ships, humans finally defeated aliens and this became the first Planet War in history. Our goal is to run a simulation of the ancient war to verify some historical hypotheses.

Producing each spaceship takes an amount of time which is constant for each planet but may vary among different planets. We call the number of spaceships each planet can produce in a year, the production rate of that planet. Note that each planet has a number of spaceships in it initially (before the simulation starts). The planets start producing ships when the simulation starts, so if a planet has nships initially, and has the production rate p, it will have n + p ships at the beginning of year 1, and n + i × p ships at the beginning of year i (years are started from zero).

Bradley Bennett, the commander in chief of the human armies, decided a strategy for the war. For each alien planet A, he chooses a corresponding human planet P, and produces spaceships in P until a certain moment at which he sends all spaceships in P to invade the planet A. No alien planet is invaded by two human planets and no human planet sends its spaceships to two different alien planets.

The defense power of the alien planets comes from their powerful mammoths. Each alien planet contains a number of mammoths initially and produces a number of mammoths each year (called the production rate of the planet). When a fight between spaceships and mammoths takes place, the side having the greater number of troops is the winner. If the spaceships win, the alien planet is defeated. In case the number of mammoths and spaceships are equal, the spaceships win.

The difficulty with planning this strategy is that it takes some time for the spaceships to reach the alien planets, and during this time, the aliens produce mammoths. The time required for spaceships to travel from each human planet to each alien planet is known. The ships can leave their planets only at the beginning of years (right after the ships are produced) and reach the alien planets at the beginning of years too (right after the mammoths are produced).

As an example, consider a human planet with two initial spaceships and production rate three invading an alien planet with two initial mammoths and production rate two. The time required to travel between the two planets is two years and the ships are ordered to leave at year one. In this case, five ships leave the human planet. When they reach the alien planet, they confront eight mammoths and will be defeated during the fight.

Bennett decided to prepare a plan that destroys every alien planet in the shortest possible time. Your task is to write a program to generate such a plan. The output is the shortest possible time (in years) in which every alien planet is defeated.

Input
There are multiple test cases in the input. The first line of each test case contains two numbers H and A which are the number of planets under the control of humans and aliens respectively (both between 1 and 250). The second line of the test case contains H non-negative integers n1 m1 n2 m2 … nH mH. The number ni is the initial number of Saber Tooth spaceships in the ith human planet and mi is the production rate of that planet. The third line contains A non-negative integers which specify the initial number of mammoths and the production rate of the alien planets in the same format as the second line. After the third line, there are H lines each containing A positive integers. The jth number on the ith line shows how many years it takes a spaceship to travel from the ith human planet to the jth alien planet. The last line of the input contains two zero numbers. Every number in the input except H and A is between 0 and 40000.

Output
The output for each test case contains a single integer which is the minimum time in which all alien planets can be defeated. If it is impossible to destroy all alien planets, the output should be IMPOSSIBLE.

Sample Input
2 1
2 3 0 3
2 2
2
2
0 0

Sample Output
6

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

2
faster-rcnn的bounding boxes是否可以改进啊
1
faster-rcnn迭代到一定次数停住了(自己数据集)
1
mask-rcnn mask像素坐标储存在哪?
3
我在网上找了个bmp转YUV的程序进行修改,但读不出数据,不知什么问题,有谁懂的请帮忙看下,谢谢了
1
CPU下实时图像分割技术。
2
新人 人脸识别 python opencv.深度学习 有一些概念性问题 求助一下
1
C++ 数据结构 创建一个二叉树,广度优先遍历。为啥结果不正确?
2
钥匙计数,这个算法问题不需要输入,只要输出就可以了,怎么做?
1
一个有关钥匙计数方面的算法问题
1
关于树的层次输出问题,请教一下我的代码为什么输出不来结果
1
有哪些移植简单又有趣的深度学习算法可以移植到Linux系统的arm开发板上?
2
表格ocr后处理 有没有 人工智能算法?
2
数据分析数据结构,有没有相关的机器学习算法? 急求大神指点
1
有没有一种机器学习算法能够从几组数据中直接输出第几组数据是最优的?
0
求助,近似动态规划算法解决车辆路径问题的实现,有偿。
0
pytorch自定义loss,如何进行后向传播loss.backward()?
1
关于opencv中dnn模块内存泄漏
0
路径的深度搜索问题,寻找路径带权绝对值的算法,运用C语言怎么实现
0
数据结构的广度优先的搜索的算法,多个路径递归怎么用 C 程序实现了
0
算法基础-打开算法之门书中65页关于计数排序的图是不是有问题啊