# 最小距离采用矩阵算法，这是不是欧拉问题，采用C语言如何解决

Problem Description

Given is a road (running East-West), with its passing points, a number of eastbound cars and a number of westbound cars. (An eastbound car enters the road at the West side). Furthermore a schedule is given, that is, for every pair (e,w), where e is an eastbound car and w is a westbound car, the place where they pass each other is given. If the cars enter the road with long delays, such a schedule may take an arbitrary long time. We assume, however, that all cars are ready to enter the road, and eager to leave the road as soon as possible. We measure the time between the moment the rst car enters the road, and the moment the last car leaves the road, and we want that interval to be as short as possible. All cars either stand still, or are driving with a constant speed of 45 km/h. Starting and stopping does not take any time. Two cars driving in the same direction always keep a distance of at least 25 meter. The distance between two different passing places is at least 30 meter. The length of the cars may be ignored.

Input
The first line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line containing the length l (0 < l <=30000) of the road in meters, and the number p(0 < p) of passing places;

A line containing p positive integers, the distance in meters from each passing place to the west end of the road. These numbers are sorted in increasing order;

A line containing two positive integers e and w, (0 < e,w <= 1000) the number of eastbound and westbound cars respectively;

e lines, containing w numbers each, indicating the passing points of each pair of cars.The number z on position x (1 <=x<= w) of line y (1 <=y <= e) indicates that the eastbound car y passes the westbound car x at passing point z (0 <=z <= p + 1).Westbound car x enters the road before westbound car x + 1, and eastbound car y enters the road before eastbound car y + 1. The value z = 0 indicates crossing at the west end, so car y enters the road after x has left the road. The value z = p+1, in the same way, indicates crossing at the east side.

All numbers on a line are each separated by one or more spaces.

Output
For each test case, the output contains one line with one number: the time (in seconds, rounded to the nearest integer) it takes to have all cars pass the road.

Sample Input
2
150 1
50
1 1
1
100 1
30
3 2
2 2
1 2
0 2

Sample Output
16
48

• 写回答

#### 1条回答默认 最新

• threenewbee 2019-12-29 00:37
关注
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 学校优化算法sbo和蚁群算法怎么结合
• ¥20 Apache poi使用问题
• ¥21 matlab怎么求时域信号的二阶导数
• ¥15 判断两个表是否完全相同
• ¥15 java map类型数据格式，如何快速通过前缀匹配元素
• ¥15 stc12c5a60s2、QMC5883L、LCD1602组合测量磁场所需程序
• ¥20 Win11测试yolov4，“找不到nvcuda.dll”怎么办？