数据结构编火车时刻调度问题的算法,怎么采用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个回答

shunfurh
shunfurh 不行啊,有水平更高的人回答么
3 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

1
关于“用C语言实现模拟操作系统进程调度先来先服务”代码中的问题
1
OOZIE与Tez执行兼容问题
1
C#如何让awit之后的代码在指定的线程执行,像winform那样保证awit之后的代码在UI线程执行
1
关于Python APScheduler调度模块的问题
1
优先数调度算法,没写成功,请大神指导一下小菜鸟,救救孩子
1
怎样在IDEA里debug调试spark源码的shuffle内存调度模块?
0
为什么我的定时调度任务每次只能执行一个任务,而且是每次最后添加的任务。
0
.net core spider【爬虫】如何进行点击页面某个控件再进行获取数据?
6
假如有一个计时器程序,当CPU调度其他程序时,计时器程序是否还在计时?
2
新手求matlab车辆调度代码 有偿
3
go协程调度的三个问题(具体看描述)?
0
Spark Task卡住的问题、Scheduler Delay 很长的问题
3
xxl-job 触发调度,提示错误:job handler not found
4
在一个调度任务中起了个线程去定时查询某状态为什么第一次启动执行的时候没问题下来启动过程中报如下错误
0
贪心算法中多机调度的问题?
3
轮船调度问题求大佬解答
0
请问该轮船调度问题该如何规划算法
0
azkaban调度工具怎么将上游job1运行得到的结果传递给下游job2,急急急
0
电梯模拟调度的算法的实现,怎么利用C程序的语言代码编写的过程去完成?
1
自动化立体车库存取车优化策略:matlab仿真程序