#P18231. Antivirus

Antivirus

Antivirus

Hyrule 即将进入流感季。

Hyrule 有 nn 座城市,由 mm 条有向道路连接,编号为 11 的城市是首都。保证从每座城市都能沿道路到达首都。

流感季持续 qq 天。第 ii 天中午,病毒从城市 aia_i 开始沿有向道路传播。传播速度很快,可以认为从 aia_i 能到达的所有城市都会立即受到感染。如果当天的病毒传播到了首都,就会造成 bib_i 的经济损失。

为了阻止病毒传播,Auru 每晚可以在一座城市部署一个病毒过滤器,包括第一天之前的那个晚上。在城市 vv 部署过滤器需要支付 cvc_v。病毒不能经过部署了过滤器的城市,这座城市本身也不会被感染。如果病毒恰好从部署了过滤器的城市开始传播,它就会直接消失,不感染任何城市。

已经部署的过滤器会一直有效,直到 Auru 在另一座城市部署新的过滤器。也就是说,任何时刻最多只能有一个有效的过滤器。

对于每个 i=1,2,…,qi=1,2,\ldots,q,只考虑前 ii 天的病毒,求“经济损失之和加上部署费用之和”的最小值。

每个前缀分别求最优方案,不要求用同一个部署策略同时实现所有前缀的最优值。

输入格式

第一行包含一个整数 TT,表示测试用例数。

对于每个测试用例:

第一行包含三个整数 n,m,qn,m,q,分别表示城市数、道路数和流感季持续天数。

接下来 mm 行,每行包含两个整数 ui,viu_i,v_i,表示一条从城市 uiu_i 到城市 viv_i 的有向道路。保证没有自环,允许重边,且每座城市都可以到达首都。

接下来一行包含 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n,表示在各座城市部署过滤器的费用。

接下来 qq 行,第 ii 行包含两个整数 ai,bia_i,b_i,表示第 ii 天病毒的起始城市,以及该病毒到达首都时造成的经济损失。

输出格式

对于每个测试用例,输出一行,共 qq 个整数。第 ii 个整数表示只考虑前 ii 天时,经济损失与部署费用之和的最小值。

样例

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 部署过滤器,总费用为 22。
  • 考虑前 2 天,在第 0 天晚上于城市 2 部署过滤器,总费用为 33。
  • 考虑前 3 天,在第 0 天晚上于城市 2 部署过滤器,在第 2 天晚上改为于城市 6 部署,总费用为 3+1=43+1=4。
  • 考虑前 4 天,在第 0 天晚上于首都部署过滤器,总费用为 44。

样例第一组的道路

第二组数据中:

  • 只考虑第 1 天,初始在城市 5 部署,总费用为 55。
  • 考虑前 2 天,初始在城市 4 部署,总费用为 100100。
  • 考虑前 3 天,初始在城市 4 部署,第 2 天晚上改为在城市 3 部署,总费用为 100+2=102100+2=102。
  • 考虑前 4 天,初始在城市 4 部署,第 2 天晚上改为在城市 3 部署,第 3 天晚上再改为在城市 4 部署,总费用为 100+2+100=202100+2+100=202。

样例第二组的道路

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

样例第三组的道路

数据范围

对于所有数据:

  • 1≤T≤1041\le T\le10^4;
  • 2≤n≤1052\le n\le10^5;
  • n−1≤m≤2×105n-1\le m\le2\times10^5;
  • 1≤q≤1051\le q\le10^5;
  • 1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i,允许重边;
  • 1≤ci≤1091\le c_i\le10^9;
  • 2≤ai≤n2\le a_i\le n;
  • 1≤bi≤1091\le b_i\le10^9。

每个输入文件中,所有测试用例的 nn 之和不超过 10510^5,mm 之和不超过 2×1052\times10^5,qq 之和不超过 10510^5。