P15184 [SWERC 2019] Environment-Friendly Travel

不幸的是，度假会产生碳足迹。每旅行一公里的 CO₂ 成本取决于交通方式。例如，火车旅行的成本低于巴士，而巴士又低于汽车。 你的目标是规划一次从你家（坐标为 $(x_s, y_s)$）到旅行目的地（坐标为 $(x_d, y_d)$）的假期行程。由于意识到旅行对环境的影响，你希望最小化假期的 CO₂ 成本，但同时仍希望将总旅行公里数控制在给定的预算 $B$ 内。 为了帮助你规划，你可以访问一张包含 $N$ 个车站的地图，这些车站可能通过 $T$ 种不同的交通方式（飞机、火车等）连接，编号为 $1, \ldots, T$。每种方式每距离单位的 CO₂ 成本为 $C_1, \ldots, C_T$。你可以开车从家到目的地、从家到任何车站、以及从任何车站到目的地，每距离单位的成本为 $C_0$。$C_0$ 总是大于 $C_1, \ldots, C_T$ 中的任何一个。 每个车站 $i$（$i = 0, \ldots, N - 1$）都有坐标 $(x_i, y_i)$。每个车站可能通过一种或多种交通方式连接到其他车站。每个连接是双向的，因此只需列出其中一个方向。两个车站之间可能有多种交通方式可用。你只能使用可用的交通方式通过车站之间的连接旅行（车站之间不允许开车旅行）。 两点 $a$ 和 $b$ 之间的距离是 $(x_a, y_a)$ 和 $(x_b, y_b)$ 之间的二维距离，向上取整到最近的整数： $$ \text{dist}(a, b) = \left\lceil \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2} \right\rceil, $$ 而使用交通方式 $i$ 在 $a$ 和 $b$ 之间旅行的 CO₂ 成本为： $$ \text{cost}(a, b, i) = C_i \times \text{dist}(a, b). $$ 给定两个源-目的地坐标、以距离单位表示的预算 $B$、交通方式列表及其各自的 CO₂ 成本，以及车站网络，你的任务是计算在最多旅行 $B$ 公里的情况下可能的最小 CO₂ 成本。

输入包含以下行： - 第 1 行包含两个空格分隔的整数 $x_s$ 和 $y_s$，你家的坐标。 - 第 2 行包含两个空格分隔的整数 $x_d$ 和 $y_d$，目的地的坐标。 - 第 3 行包含一个整数 $B$，你接受的最大旅行距离（公里）。 - 第 4 行包含一个整数 $C_0$，开车旅行每距离单位的 CO₂ 成本。 - 第 5 行包含一个整数 $T$，交通方式的数量（除汽车外）。 - 对于 $1 \leq i \leq T$，第 $i + 5$ 行包含整数 $C_i$，交通方式 $i$ 每距离单位的 CO₂ 成本。 - 第 $T + 6$ 行包含整数 $N$，车站的数量。 - 对于 $0 \leq i < N$，第 $i + T + 7$ 行描述车站 $i$，包含 $3 + 2 \times l_i$ 个空格分隔的整数。前三个整数是 $x_i$、$y_i$ 和 $l_i$。$(x_i, y_i)$ 表示车站 $i$ 的坐标，而 $l_i$ 是车站 $i$ 与其他车站之间的连接数。剩余的 $l_i$ 对整数 $(j, m_j)$ 各描述一个到车站 $j$（$0 \leq j < N$）的连接，使用交通方式 $m_j$（$1 \leq m_j \leq T$）。所有连接都是双向的。

输出应包含一行，一个整数，表示在公里预算内可达到的最小 CO₂ 成本；如果找不到可行的成本，则输出 $-1$。

#### 样例解释 结果对应以下路线的 CO₂ 成本： 1. 从家 $(1,1)$ 开车到车站 0 $(2,3)$，成本为 $100 \times \left\lceil \sqrt{1^2 + 2^2} \right\rceil = 300$， 2. 通过交通方式 2 到车站 2 $(9,3)$，成本为 $50 \times \left\lceil \sqrt{7^2 + 0^2} \right\rceil = 350$， 3. 开车到目的地 $(10,2)$，成本为 $100 \times \left\lceil \sqrt{1^2 + 1^2} \right\rceil = 200$，总计 850。 该路线有效，因为总旅行距离为 $3 + 7 + 2 = 12$，在允许的预算 12 内。 #### 数据范围 所有输入均为整数。所有坐标在 $[0, 100] \times [0, 100]$ 范围内。 - $1 \leq T \leq 100$； - $1 \leq N \leq 1000$； - $0 \leq B \leq 100$； - $1 \leq C_1, \ldots, C_T < C_0 \leq 100$； - 每个车站最多有 100 条到其他车站的连接。 翻译由 DeepSeek 完成