P14038 [PAIO 2025] Adventure Plan
题目背景
**不要** $\texttt{\#include "adventure.h"}$。**使用 C++>=17** 提交。
题目描述
### 冒险计划
你正在为一次冒险做准备。这次冒险是在一个有向无环图（DAG）上的从起点到终点的旅程。该 DAG 有 $n$ 个顶点，编号为 $0$ 到 $n-1$，以及 $m$ 条边。起点是顶点 $0$，且所有顶点都可从起点到达。
每条从 $u_i$ 到 $v_i$ 的有向边都有两个属性：$l_i$ 和 $r_i$。它表示安全通过该边所需的最小和最大时间。因此，你可以为该边设定计划通过时间 $t_i$，满足 $t_i$ 是区间 $[l_i, r_i]$ 内的任意整数。
你的许多朋友也正在为冒险做准备。每个人都会选择一条不同的从起点到终点的路径。为了保证安全，你希望选择每条边的计划通过时间，使得从起点到任意顶点 $u$ 的所有路径消耗的总时间都相同。也就是说，希望对每个顶点 $u$，所有从起点到 $u$ 的路径，它们的总用时都一样。
我们称图满足上述要求时为“安全”的。保证初始的图是安全的。
### 任务 1
你想向图中添加一些新边，使其更加有趣。你将执行 $q$ 次“添加新边”的操作。每次操作会给出一条新的有向边 $(u_i, v_i, l_i, r_i)$。你已知添加这条边后，图依然是有向无环图，但不确定图是否仍然安全。请判断添加该边后图是否安全。如果安全，就将该边添加到图中；否则，忽略这次操作。
### 任务 2
所有操作结束后，你需要为每条边（包括新增边）输出一个计划通过时间 $t_i$，以证明你能确保新图依然安全。
### 实现细节
你需要实现两个过程：
第一个过程是 `add_roads`：
```cpp
boolean[] add_roads(int32 N, int32 M, int32 Q,
int32[] U, int32[] V,
int32[] L, int32[] R,
int32[] U2, int32[] V2,
int32[] L2, int32[] R2);
```
- $N$：顶点数；
- $M$：初始边数；
- $Q$：操作数；
- $U, V$：长度为 $M$ 的数组，第 $i$ 条有向边为 $(U[i], V[i])$；
- $L, R$：长度为 $M$ 的数组，第 $i$ 条边的可选时间区间为 $[L[i], R[i]]$；
- $U2, V2, L2, R2$：长度为 $Q$ 的数组，描述每个新添加的边；
- 本过程在每个测试用例开始时恰好调用一次。
本过程需返回一个长度为 $Q$ 的数组，第 $i$ 个元素为 true 当且仅当执行第 $i$ 次操作时将该边添加进图，否则为 false。
第二个过程是 `assign_times`：
```cpp
int32[] assign_times();
```
- 本过程在每个测试用例的 `add_roads` 调用结束后恰好调用一次。
本过程需返回一个数组，依次给出最终图中每条边的计划时间 $t_i$（输出顺序任意合法即可）。
输入格式
无特殊输入格式说明，见样例与题目描述。
输出格式
无特殊输出格式说明，见样例与题目描述。
说明/提示
### 样例
#### 样例 1
考虑如下调用：
```cpp
add_roads(4, 4, 2,
[0, 1, 0, 0],
[1, 3, 3, 2],
[1, 3, 9, 6],
[5, 7, 14, 8],
[2, 2],
[3, 3],
[7, 5],
[11, 7]);
```
该过程应返回 `[false, true]`。
在 `add_roads` 调用后，若输入：
```cpp
assign_times();
```
应返回 `[5, 7, 12, 6, 6]`。
### 样例评测器
样例评测器将输入数据读入格式如下：
- 第 1 行：三个整数 $n, m, q$
- 接下来的 $m$ 行：每行四个整数 $u_i, v_i, l_i, r_i$，描述一条初始边
- 接下来的 $q$ 行：每行四个整数 $u_i, v_i, l_i, r_i$，描述一次操作
# 提示
- $3 \le n \le 500$
- $n-1 \le m \le 10^5$
- $0 \le q \le 500$
- $0 \le u_i < n$
- $1 \le l_i \le r_i \le 10^9$
# 评分
1. 子任务 1（7 分）：$n \le 3$
2. 子任务 2（21 分）：$q = 0$
3. 子任务 3（12 分）：$v_i = u_i + 1$
4. 子任务 4（11 分）：$l_i = r_i$
5. 子任务 5（24 分）：$n \le 100, m \le 100, q \le 100$
6. 子任务 6（25 分）：无额外约束。
由 ChatGPT 5 翻译