#59. 星际物流调度系统

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wangjunyi2013

题目描述

在遥远的未来,人类已经开拓了多个星际殖民地,并且建立了一个庞大的星际物流网络。你需要编写一个程序来模拟这个星际物流调度系统的运行。 基本设定

  1. 星系与殖民地:存在多个星系,每个星系中有若干个殖民地。每个殖民地有唯一的编号,并且有一定的货物存储量。
  2. 运输飞船:有不同类型的运输飞船,每种飞船有不同的载货量和飞行速度。飞船可以在星系内的殖民地之间以及不同星系的殖民地之间飞行。
  3. 任务:每个任务包含一个起始殖民地和一个目标殖民地,以及需要运输的货物量。

输入格式

第一行包含两个整数 ,分别表示星系的数量和殖民地的总数。

接下来的 行,每行包含三个整数 ,分别表示该殖民地所在的星系编号、殖民地编号和初始货物存储量。

下一行包含一个整数 ,表示运输飞船的数量。

接下来的 行,每行包含三个整数 ,分别表示飞船的编号、载货量和飞行速度。

下一行包含一个整数 ,表示任务的数量。

接下来的 行,每行包含四个整数 ,分别表示任务的编号、起始殖民地编号、目标殖民地编号和需 要运输的货物量。

输出格式

输出每个任务完成的时间(以时间单位计),如果任务无法完成,输出

规则与限制

  1. 飞船调度:你需要合理调度飞船来完成任务。飞船可以同时执行多个任务,但每次只能运输一个任务的货物。
  2. 飞行时间:飞船在星系内的飞行时间为两个殖民地之间的距离(假设为 个时间单位),在不同星系之间的飞行时间为 个时间单位。
  3. 货物装卸:货物的装卸时间忽略不计。
  4. 货物充足性:起始殖民地必须有足够的货物才能开始任务。

样例

样例#1

输入样例#1

2 4
0 0 100
0 1 200
1 2 300
1 3 400
2
0 50 1
1 100 2
3
0 0 2 50
1 1 3 100
2 2 0 200

输出样例#1

6
6
-1