5087：农产品运输
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 农产品运输
## 题目描述
一家农业合作社需要将新鲜农产品从种植基地 $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$ 的运输路线。
## 输出格式
输出一个整数，表示最小的总成本。
## 样例
### 样例输入 1
```text
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
```
### 样例输出 1
```text
32
```
### 样例输入 2
```text
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
```
### 样例输出 2
```text
5
```
### 样例输入 3
```text
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
```
### 样例输出 3
```text
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$ | 无 |
---
**题目来源：** 25年6月-C组（大咖）