#P18231. Antivirus
Antivirus
Antivirus
Hyrule 即将进入流感季。
Hyrule 有 座城市,由 条有向道路连接,编号为 的城市是首都。保证从每座城市都能沿道路到达首都。
流感季持续 天。第 天中午,病毒从城市 开始沿有向道路传播。传播速度很快,可以认为从 能到达的所有城市都会立即受到感染。如果当天的病毒传播到了首都,就会造成 的经济损失。
为了阻止病毒传播,Auru 每晚可以在一座城市部署一个病毒过滤器,包括第一天之前的那个晚上。在城市 部署过滤器需要支付 。病毒不能经过部署了过滤器的城市,这座城市本身也不会被感染。如果病毒恰好从部署了过滤器的城市开始传播,它就会直接消失,不感染任何城市。
已经部署的过滤器会一直有效,直到 Auru 在另一座城市部署新的过滤器。也就是说,任何时刻最多只能有一个有效的过滤器。
对于每个 ,只考虑前 天的病毒,求“经济损失之和加上部署费用之和”的最小值。
每个前缀分别求最优方案,不要求用同一个部署策略同时实现所有前缀的最优值。
输入格式
第一行包含一个整数 ,表示测试用例数。
对于每个测试用例:
第一行包含三个整数 ,分别表示城市数、道路数和流感季持续天数。
接下来 行,每行包含两个整数 ,表示一条从城市 到城市 的有向道路。保证没有自环,允许重边,且每座城市都可以到达首都。
接下来一行包含 个整数 ,表示在各座城市部署过滤器的费用。
接下来 行,第 行包含两个整数 ,表示第 天病毒的起始城市,以及该病毒到达首都时造成的经济损失。
输出格式
对于每个测试用例,输出一行,共 个整数。第 个整数表示只考虑前 天时,经济损失与部署费用之和的最小值。
样例
3
7 6 4
2 1
3 1
4 2
5 2
6 3
7 3
4 3 5 2 2 1 1
4 2
5 2
6 2
7 2
5 6 4
1 3
3 2
2 1
4 2
5 4
2 5
10000 10000 2 100 5
5 1000
4 1000
3 1000
4 1000
4 4 1
2 1
3 1
4 2
4 3
100 1 1 100
4 10
2 3 4 4
5 100 102 202
10
样例说明
第一组数据中:
- 只考虑第 1 天,在第 0 天晚上于城市 4 部署过滤器,总费用为 。
- 考虑前 2 天,在第 0 天晚上于城市 2 部署过滤器,总费用为 。
- 考虑前 3 天,在第 0 天晚上于城市 2 部署过滤器,在第 2 天晚上改为于城市 6 部署,总费用为 。
- 考虑前 4 天,在第 0 天晚上于首都部署过滤器,总费用为 。

第二组数据中:
- 只考虑第 1 天,初始在城市 5 部署,总费用为 。
- 考虑前 2 天,初始在城市 4 部署,总费用为 。
- 考虑前 3 天,初始在城市 4 部署,第 2 天晚上改为在城市 3 部署,总费用为 。
- 考虑前 4 天,初始在城市 4 部署,第 2 天晚上改为在城市 3 部署,第 3 天晚上再改为在城市 4 部署,总费用为 。

第三组数据中,不能同时在城市 2 和城市 3 部署过滤器。城市 1、4 的部署费用都超过当天的经济损失,因此不部署过滤器、承担 的损失就是最优方案。

数据范围
对于所有数据:
- ;
- ;
- ;
- ;
- ,,允许重边;
- ;
- ;
- 。
每个输入文件中,所有测试用例的 之和不超过 , 之和不超过 , 之和不超过 。