编程介的小学生 2019-06-03 14:55 采纳率: 20.5%
浏览 150

数据结构编火车时刻调度问题的算法,怎么采用C语言的程序代码编写的技术和步骤去实现程序的呢?

Problem Description
Elihc is a strange country occupying a long, narrow strip of land from north to south. There is only one main railway line in this country. This railway line is a straight line. It starts from the northernmost station, traverses the whole country southward, and finishes at the southernmost station.

Unfortunately, there are too many trains travelling on this railway line all the time. Long delays, even serious railway accidents are quite common here. Now, Railways Bureau of Elihc decides to solve these problems by scheduling the train in a better way, and hires you to write the program.

There are (N+1) stations on this railway line, and they are numbered from 0 to N from north to south. There are also M trains numbered from 0 to M-1. Each train has an initial station, a terminal station, expected time of departure and speed limit. Initially, it parks at its initial station. It departs at the expected time or after the expected time, and is bound for its terminal station. The train has to stop at every station on its route. Different trains may have different speed limits. During the journey, a train should always run within its own speed limit (it is allowed to run at any speed not exceeding the limit anywhere). Compared with the railway line, both stations and trains are so small that they can be regarded as points in your scheduling program.

For each pair of adjacent stations, the part of the railway line between them is called a section (stations are not included). The positions of the stations are well designed so that the length of each section is exactly S kilometer. All stations are sufficient to park any number of trains. However, due to some financial difficulties, there is just one track for each section. For safety reasons, trains running on the same section should always follow the rules below.

  1. They are running in the same direction.
  2. A train can catch up with, but can never pass any other trains in front of it.

An officer of Railways Bureau provides you some scheduling strategies, which you have to use in your program:

  1. During scheduling, trains that are not expected to depart yet should be ignored. If a train has already arrived at its terminal station, it will be ignored forever.
  2. Once a train is expected to depart from the original station, or arrives at a station except the terminal one, it stops and waits to move on the next section immediately.
  3. When a train is stopping in some station, it will not start to move to the next section until (1) no running train is coming from the opposite direction on this section, and (2) No train with smaller number is stopping and waiting to move on this section from station at either end of this section.
  4. A train should always run as fast as it can, without passing any train in front running on the same section.

Now, please help Railways Bureau to schedule the trains and figure out when each train will reach its terminal station.

Input
There are several test cases in the input.

The first line contains an integer C (1 ≤ C ≤ 10) -- the number of test cases.

Each test case begins with three integers N, M, S (1 ≤ N ≤ 10, 1 ≤ M ≤ 10, 1 ≤ S ≤ 1000), indicating the number of stations, the number of trains and the length of section (in kilometer).

Then M lines follow, describing trains from number 0 to M-1 in order, one per line. Each line contains four integers O, T, E, L (0 ≤ O ≤ N, 0 ≤ T ≤ N, O ≠ T, 0 ≤ E ≤ 10000, 1 ≤ L ≤ S), indicate that this train travels from station O to station T, expected to depart at minute E, and its speed limit is L kilometer per minute.

Output
For each test case, output the arrival time (in minute) of each train one per line, in ascending order of train number. Your answers should be rounded up to the nearest integer.

Sample Input
2
1 3 100
0 1 0 5
0 1 20 5
1 0 0 5
2 2 100
0 2 0 4
0 2 2 5

Sample Output
20
40
60
50
50

  • 写回答

1条回答 默认 最新

  • Next66 2019-06-03 15:00
    关注
    评论

报告相同问题?

悬赏问题

  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择