该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2311.zip](file://AdditionalFile2311.zip?type=additional_file)

#2311. 「ZJOI2006」物流运输

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

给出 $n$ 个点 $m$ 条边 的无向图，总共有 $t$ 天，要求每天走一条从点 $1$ 到点 $n$ 的路径，使得总 $t$ 天的总费用最小。

1、部分点在一段时间内无法通过。保证任何一天都存在至少一条从码头 $1$ 到码头 $n$ 的运输路线。

2、若 第 $i+1$ 天 和 第 $i$ 天的路线不同，则增加修改成本 $v$。

输入格式

第一行四个整数 $t,n,v,m \ ( 1\le t\le 100，1\le n\le 20)$。

接下来 $m$ 行，每行三个整数 $x,y,w(1\le x, y\le n , 1 \le w \le 100 )$ ，依次表示一条无向边的两个点 $x,y$ 以及通过该边的费用 $w$。

下来一个整数 $q$。

下来 $q$ 行每行是三个整数 $x,a,b \ ( 1 \le x \le n ,1 \le a\le b\le t)$。表示点 $x$ 从第 $a$ 天到第 $b$ 天无法通过（含头尾）。同一个点有可能在多个时间段内无法通过。

输出格式

一个整数表示最小的总成本。总成本 $=t$ 天运输路线长度之和 $+v\times$ 改变运输路线的次数。

样例

输入

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$ 天的情况，阴影表示不可用的码头。

最优方案为：前三天走 $1\rightarrow 4\rightarrow 5$，后两天走 $1\rightarrow 3\rightarrow 5$，这样总成本为 $(2+2)\times 3+(3+2)\times 2+10=32$。