说明

城市规划

城市规划包括单向街道和交叉口。每条街道：

• 由一个唯一的名称标识，
• 从一个交叉口通向另一个交叉口，
• 中间不包含任何交叉口（如果两条街道需要在交叉口外交叉，则使用桥梁或隧道），
• 有一个固定的时间 $L$，表示一辆车从街道起点到终点所需的时间。如果一条街道的通行时间为 $L$ 秒，一辆车在时间 $T$ 进入该街道，那么它将在 $T + L$ 时刻精确到达街道终点，与街道上有多少车辆无关。

:::align{center} :::

图 1. 一个包含 4 个交叉口（0、1、2 和 3）和 7 条街道（a、b、……、g 街）的城市规划。

交叉口 0 和 2 通过 a 街和 b 街双向直接连接。c 街使用一座桥梁跨越 a 街和 b 街，不与这两条街道相交。

注意，虽然街道是单向的，但仍然可能有两个单向街道以相反方向连接两个交叉口（见图 1 中的交叉口 0 和 2 以及 a 街和 b 街）。但是，永远不会有两条街道以相同方向连接两个交叉口。

每个交叉口：

• 有一个唯一的整数 ID（例如 $0, 1, 2, \ldots$），
• 至少有一条街道进入它，并且至少有一条街道从它引出。

交通信号灯

每条街道的终点（紧邻交叉口前）都有一个交通信号灯。每个交通信号灯有两种状态：绿灯表示该街道的车辆可以穿过交叉口并前往任何其他街道，红灯表示该街道的车辆需要停止。在任何给定时间，每个交叉口最多有一个交通信号灯是绿灯。当进入街道的绿灯亮起时，只有来自该街道的车辆被允许进入交叉口（并移动到任何引出街道），所有其他车辆必须等待。

排队

当街道终点的信号灯为红色时，到达的车辆排队等待绿灯。当绿灯亮起时，每秒可以有一辆车通过交叉口。 这意味着，如果给定街道的绿灯持续 $T_i$ 秒，那么只有该街道的前 $T_i$ 辆车将继续行驶（见图 2）。其他车辆需要等待下一个绿灯。

:::align{center}

:::

图 2. 考虑一个具有两条进入街道（a 街有 3 辆等待车辆，b 街有 2 辆等待车辆）和两条引出街道（c 街和 d 街）的交叉口。有两个交通信号灯，一个在 a 街终点，$T_1 = 2$；一个在 b 街终点，$T_2 = 3$。最初，a 街的信号灯是绿灯，第一辆（黄色）车开始移动。在 $T = 1$ 时，a 街的下一辆（绿色）车开始移动。在 $T = 2$ 时，a 街变为红灯，最后一辆（红色）等待的车辆需要停止。同时，b 街的信号灯变为绿灯，第一辆（紫色）排队车辆开始移动。在 $T = 3$ 和 $T = 4$ 时，最初在 b 街上的两辆（紫色和蓝色）车已经通过了信号灯并继续行驶。在 $T = 5$ 时，a 街的信号灯再次变为绿灯，等待的（红色）车现在可以移动。

调度

对于每个交叉口，我们可以设置一个交通信号灯调度。交通信号灯调度决定了该交叉口进入街道绿灯的顺序和持续时间，并重复直到模拟结束。调度是一个配对列表：进入街道和持续时间。每条街道在调度中最多出现一次。 调度可以忽略一些进入街道——那些街道将永远不会获得绿灯。

交通信号灯调度由你的提交控制。你不必指定所有交通信号灯的调度。默认情况下，所有交叉口的所有信号灯都是红色的（是的，被困在那里的车辆将不得不等待直到模拟结束）。

交通信号灯调度示例

在以下示例中，一个交叉口有 3 条街道通向它（a、b 和 c 街），以及一条离开交叉口的街道（d 街）。我们考虑这些交通信号灯的三种不同调度示例：

无交通信号灯调度（默认）。

:::align{center} :::

图 4（a）。如果没有为交叉口设置交通信号灯调度，所有信号灯在整个模拟期间保持红色。任何计划通过 a、b 或 c 街的车辆将被阻塞，无法到达目的地。

仅覆盖一条街道的调度。

:::align{center} :::

图 4（b）。在此示例中，交通信号灯调度仅覆盖一条进入街道（b 街）。在这种情况下，b 街始终是绿灯。任何来自 b 街的车辆将总是直接通过交叉口，而任何计划通过 a 街或 c 街的车辆将被阻塞，无法到达目的地。

覆盖所有街道的调度。

:::align{center} :::

图 4（c）。在此示例中，交通信号灯调度覆盖所有进入街道（先是 c 街，然后是 a 街，然后是 b 街）。对于每条街道，我们可以定义不同的 $T_i$，意味着该信号灯保持绿灯的不同持续时间。

车辆

每辆车由其行驶的路径（街道序列）描述。路径由输入数据集定义且不可更改。在输入数据集中，我们保证每辆车最多通过同一个交叉口一次。

最初，所有车辆从它们路径中第一条街道的终点开始，等待绿灯（如果信号灯是红色），或准备移动（如果是绿灯）。如果两辆车从同一条街道的终点开始，输入文件中列出的第一辆车先行。然后每辆车遵循给定路径，同时遵守交通信号灯，并需要到达该路径中最后一条街道的终点。

车辆在每条街道的终点排队。队列中的第一辆车可以在绿灯亮起后立即通过交叉口。车辆通过交叉口时没有延迟。之后的车辆每秒一辆依次通过交叉口。

当一辆车进入其路径的最后一条街道时，它会一直行驶到该街道的终点，然后立即被移除。这意味着该车不会在其路径的最后一条街道终点排队，也不会进入其终点的交叉口。

:::align{center} :::

图 3. 此图显示了在精确 $T$ 秒时三辆车的状态，模拟从 $T = 0$ 开始，到 $T = 5$ 结束。街道的 $L = 3$，意味着任何车辆需要 3 秒从其起点到终点。左侧交叉口的绿灯在 $T = 1$ 时亮起，并在 2 秒后再次变红。车辆在街道终点排队，黄色车是第一辆。在 $T = 1$ 时，第一辆（黄色）车立即开始移动，并在 3 秒后，即 $T = 4$ 时到达街道终点。第二辆（红色）车必须等待 1 秒才能开始移动，并在 3 秒后，即 $T = 5$ 时到达街道终点。第三辆（紫色）车没有足够时间进入街道，因为信号灯已经变红。注意，为简单起见，此图仅显示两条街道：当显示信号灯为红色时，这意味着同一交叉口中的另一个信号灯变为绿灯。

输入格式

输入数据 完整输入（压缩）

文件格式

每个输入数据集以纯文本文件提供。文件仅包含 ASCII 字符，行以单个 \n 字符（也称为“UNIX 风格”行结尾）结束。当一行中给出多个数字时，它们之间用单个空格分隔。

第一行包含五个数字：

• 一个整数 $D$ ($1 \leq D \leq 10^4$) - 模拟的持续时间，以秒为单位，
• 一个整数 $I$ ($2 \leq I \leq 10^5$) - 交叉口的数量（ID 从 0 到 $I - 1$），
• 一个整数 $S$ ($2 \leq S \leq 10^5$) - 街道的数量，
• 一个整数 $V$ ($1 \leq V \leq 10^3$) - 车辆的数量，
• 一个整数 $F$ ($1 \leq F \leq 10^3$) - 每辆车在时间 $D$ 前到达目的地所获得的奖励分数。

接下来的 $S$ 行包含街道的描述。每行包含：

• 两个整数 $B$ ($0 \leq B < I$) 和 $E$ ($0 \leq E < D$) - 分别是街道起点和终点的交叉口，
• 街道名称（一个由 3 到 30 个小写 ASCII 字符 a-z 和字符 - 组成的字符串），
• 一个整数 $L$ ($1 \leq L \leq D$) - 一辆车从该街道起点到终点所需的时间。

接下来的 $V$ 行描述每辆车的路径。每行包含：

• 一个整数 $P$ ($2 \leq P \leq 10^3$) - 车辆想要行驶的街道数量，
• 后跟 $P$ 个街道名称：车辆从第一条街道的终点开始（即它等待绿灯以移动到下一条街道），并沿着路径直到最后一条街道的终点。车辆的路径总是有效的，即街道将通过交叉口连接。

输出格式

你的提交描述了你想要为特定交叉口设置的交通信号灯调度。

文件格式

第一行必须包含一个整数 $A$ ($0 \leq A \leq I$)，即你指定调度的交叉口数量。

然后，提交文件必须以任意顺序描述交叉口调度。每个调度必须由多行描述：

• 第一行包含一个整数 $i$ ($0 \leq i < I$) – 交叉口的 ID，
• 第二行包含一个整数 $E_i$ ($0 < E_i$) – 此调度覆盖的进入街道（属于交叉口 $i$）的数量，
• $E_i$ 行描述绿灯的顺序和持续时间。每行必须包含（由单个空格分隔）：
  • 街道名称，
  • 一个整数 $T$ ($1 \leq T \leq D$) 表示每条街道绿灯将持续的时间。

每个交叉口在提交文件中只能列出一次。并且每个街道名称在每个调度中只能列出一次。如果街道名称未出现在交叉口配置中，则其信号灯始终为红色。如果交叉口配置未出现在提交文件中，则其所有信号灯始终为红色。

6 4 5 2 1000
2 0 rue-de-londres 1
0 1 rue-d-amsterdam 1
3 1 rue-d-athenes 1
2 3 rue-de-rome 2
1 2 rue-de-moscou 3
4 rue-de-londres rue-d-amsterdam rue-de-moscou rue-de-rome
3 rue-d-athenes rue-de-moscou rue-de-londres

3
1
2
rue-d-athenes 2
rue-d-amsterdam 1
0
1
rue-de-londres 2
2
1
rue-de-moscou 1

提示

示例

输入文件	描述
6 4 5 2 1000	6 秒，4 个交叉口，5 条街道，2 辆车，准时到达目的地奖励 1000 分。
2 0 rue-de-londres 1	街道 rue-de-londres 从交叉口 2 开始，到 0 结束，且 $L=1$。
0 1 rue-d-amsterdam 1	街道 rue-d-amsterdam 从交叉口 0 开始，到 1 结束，且 $L=1$。
3 1 rue-d-athenes 1	街道 rue-d-athenes 从交叉口 3 开始，到 1 结束，且 $L=1$。
2 3 rue-de-rome 2	街道 rue-de-rome 从交叉口 2 开始，到 3 结束，且 $L=2$。
1 2 rue-de-moscou 3	街道 rue-de-moscou 从交叉口 1 开始，到 2 结束，且 $L=3$。
4 rue-de-londres rue-d-amsterdam rue-de-moscou rue-de-rome	第一辆车从 rue-de-londres 的终点开始，然后遵循给定路径。
3 rue-d-athenes rue-de-moscou rue-de-londres	第二辆车从 rue-d-athenes 的终点开始，然后遵循给定路径。

:::align{center} :::

提交文件	描述
3	有 3 个交叉口设有交通信号灯调度：
1	在交叉口 1，交通信号灯对以下街道为绿灯
2	2 条不同的进入街道，即
rue-d-athenes 2	rue-d-athenes 绿灯 2 秒，然后
rue-d-amsterdam 1	rue-d-amsterdam 绿灯 1 秒，然后再回到 rue-d-athenes。
0	在交叉口 0，交通信号灯对
1	仅 1 条进入街道为绿灯，即
rue-de-londres 2	rue-de-londres 每周期绿灯 2 秒（对 rue-de-londres 始终为绿灯）。
2	在交叉口 2，交通信号灯对
1	仅 1 条进入街道为绿灯，即
rue-de-moscou 1	rue-de-moscou 每周期绿灯 1 秒（对 rue-de-moscou 始终为绿灯）。

评分

每辆在模拟结束前完成其路径的车辆都会获得分数。对于在时间 $T$ 完成路径的车辆，奖励分数为 $F$ 分（完成路径的固定奖励），外加 $D - T$ 分。（车辆完成路径时每剩余一秒得一分。）

换句话说：如果一辆车在时间 $T$ 完成，则得分为

• 如果 $T \leq D$，则为 $F + (D - T)$ 分，
• 否则为 0 分。

解决方案的分数是所有车辆的分数之和。

示例

例如，在上面的示例中，第一辆车：

• $T = 0$：立即通过交叉口 0，因为那里的交通信号灯始终是绿灯，
• $T = 1$：一秒后，它已经通过了 rue-d-amsterdam。然而，信号灯是红色的（因为对于交叉口 1，提交已将 rue-d-athenes 的信号灯设置为绿灯持续 2 秒），
• $T = 2$：该车现在通过交叉口并继续前往 rue-de-moscou，
• $T = 5$：该车到达 rue-de-moscou 的终点，发现交叉口 2 是绿灯，通过它并继续前往 rue-de-rome。

第一辆车本应在 $T = 7$ 时到达 rue-de-rome 的终点，但这超过了运行截止时间（在输入数据集中定义）。这意味着该车获得 0 分。

第二辆车：

• $T = 0$：发现交叉口 1 是绿灯并继续前往 rue-de-moscou，
• $T = 3$：到达 rue-de-moscou 的终点，发现交叉口 2 是绿灯且没有车辆等待，因此立即通过交叉口并前往 rue-de-londres，
• $T = 4$：该车到达 rue-de-londres 的终点，即其目的地。

因此第二辆车在截止时间前完成，并获得 $1000 + (6 - 4) = 1002$ 分。

此提交的最终分数为 1002。

注意，有多个数据集代表问题的单独实例。你团队的最终得分将是各个数据集最佳得分的总和。

你需要在本题中获得总共不低于 9700000 分，才可以被视作通过本题。赛场上的最高分是 10586135 分。

翻译由 DeepSeek 完成