SP7404 ONTIME - Just on Time
题目描述
上周关于健康和环保出行的宣传活动取得了极大的成功。数以百计的通勤者选择将小汽车换成公交或地铁，给出了积极的反馈。唯一令他们稍有不满的是，为了准时到达校园，他们必须更早地起床。
现在，你的任务就是帮助他们调整出行计划，告知他们最晚可以什么时候出发，以便在 8:15 之前到达校园。可以采用任何方式来延长他们的睡眠时间，并且大家都愿意在旅途中多次换乘不同线路的公交或地铁来实现这一目标。
公共交通网络包含 $S (0 \le S \le 100)$ 个车站（编号从 1 到 $S$），以及 $C (0 \le C \le 1000)$ 条单向连接。每条连接在某个早晨开始定时运行，直到8:15结束。需要注意的是，任意两站之间可能存在多个不同的直达服务，起始时间和频率各不相同。你需要解决一些学生提出的请求，告知他们最晚可以什么时候从家出发，才能不迟到。
输入格式
输入包括多个测试用例，每个用例之间用空行分隔。每组用例开始是包含三个整数的行，表示车站数量 $S$、连接数量 $C$ 以及请求数量 $R$。接下来有 $C$ 行，每行描述一条班车服务，格式为“起点 终点 初次发车时间 旅行时间 发车频率（分钟）”。之后是 $R$ 行，每行两个整数，第一个表示学生离家最近的车站编号（因时间太早，他们不愿多走），第二个表示学生到达该车站需要的时间（分钟）。校园位于第 $S$ 号车站。输入以一组 $S=C=R=0$ 的数据结束，这组数据不需处理。
输出格式
对于每个请求，按输入顺序给出答复。每条答复以“Leave no later than ‘时间’”格式输出，其中‘时间’以 _hh:mm_ 显示。每组用例之后添加一个空行。如果没有办法按时到达，请输出“Doomed to be late”。假设通勤者转乘公交非常熟练，可以忽略换乘时间。
**样例输入**
```
3 2 2
1 3 07:10 50 15
2 3 08:20 5 5
1 3
2 0
3 4 3
2 3 05:30 6 5
1 3 06:11 5 15
1 2 07:01 2 5
3 2 08:00 1 8
1 2
2 1
3 10
0 0 0
```
**样例输出**
```
Leave no later than 07:22
Doomed to be late
Leave no later than 07:59
Leave no later than 08:04
Leave no later than 08:05
```
**本翻译由 AI 自动生成**