4065 - 农产品运输
题目描述
一家农业合作社需要将新鲜农产品从种植基地 S 运送到加工厂 T。由于农产品产量巨大，运输任务需要连续 N 天完成。在运输过程中，农产品需要通过若干集散点进行中转。
为方便管理，合作社通常会规划一条固定的运输路线。然而，由于季节性天气或道路维护等原因，某些集散点在特定日期可能无法正常使用。此时，合作社需要调整运输路线以确保农产品顺利送达加工厂。
农产品运输，本身存在运输成本。调整运输路线会增加额外的调度成本，因此合作社希望制定一个 N 天的运输计划，使总成本最小。
总成本由：每日运输路线的总距离费用（每单位距离费用为 1 元），加上调整路线的固定调度成本构成。
更加详细的讲，总成本 = N 天运输路线距离之和 + P \times 调整运输路线的次数。（P 为每次调整运输路线的固定的调度成本）
你的任务是帮助合作社计算最优的 N 天运输计划，求出最小的总成本。
输入
第一行读入四个整数 N, M, P, E，含义如下。
- N 表示运输任务所需的天数。
- M 表示集散点总数（种植基地 S 编号为 1，加工厂 T 编号为 M）。
- P 表示每次调整运输路线所需的固定调度成本。
- E 表示可用的运输路线数量。
接下来 E 行，每行包含三个整数 U_i, V_i, L_i，表示一条连接集散点 U_i 和 V_i 的双向运输路线，路线距离为 L_i。
接下来一行包含一个整数 C，表示集散点不可用的记录数。随后 C 行，每行包含三个整数 X_i, A_i, B_i，表示编号为 X_i 的集散点在第 A_i 天到第 B_i 天（包含 A_i 和 B_i）无法使用。同一个集散点可能在多个时间段不可用，但任何时候都存在至少一条从 S 到 T 的运输路线。
输出
输出一个整数，表示最小的总成本。
样例
输入
5 5 10 8 1 2 1 1 3 3 1 4 2 2 3 2 2 4 4 3 4 1 3 5 2 4 5 2 4 2 2 3 3 1 1 3 3 3 4 4 5
输出
32
输入
1 5 100 8 2 1 6 3 1 2 4 1 5 3 2 8 4 2 9 2 5 10 5 3 3 4 5 9 1 2 1 1
输出
5
输入
10 10 20 36 2 1 2 1 3 5 1 4 6 1 5 8 1 6 10 7 1 7 1 8 9 2 3 6 4 2 3 2 5 5 2 6 3 7 2 4 8 2 6 2 9 9 4 3 8 6 3 5 3 7 3 8 3 5 3 9 6 10 3 7 4 5 9 4 6 1 7 4 9 4 8 5 4 9 5 10 4 9 5 8 1 6 7 8 8 6 2 6 10 10 7 8 3 9 7 2 10 7 8 8 9 8 8 10 9 9 10 6 11 4 4 10 9 4 10 5 1 8 3 1 8 6 10 10 6 1 3 5 10 10 8 6 9 2 6 9 7 10 10 6 6 8
输出
164
说明
样例 1 解释
- 前三天使用路线 1 \to 4 \to 5，每日距离为 2 + 2 = 4，三天总距离费用为 4 \times 3 = 12。
- 后两天调整为路线 1 \to 3 \to 5，每日距离为 3 + 2 = 5，两天总距离费用为 5 \times 2 = 10。
- 调整路线一次，额外的调度成本为 10。总成本为 12 + 10 + 10 = 32。
数据范围
对于所有的测评数据，满足：
- 1 \leq N \leq 100，1 \leq M \leq 20，1 \leq P \leq 500，1 \leq E \leq 200。
- 1 \leq U_i, V_i \leq M，1 \le L_i \le 100。
- 1 \le C \le 50，1 \le X_i \le M，1 \le A_i \le B_i \le N。
| 测试点 | 特殊性质 |
|---|---|
| 1 | N=1 |
| 2 \sim 10 | 无 |
标签