bzoj#P3691. 游行

游行

题目描述

每年春季,在某岛屿上都会举行游行活动。

在这个岛屿上有 NN 个城市,MM 条连接着城市的有向道路。

你要安排英雄们的巡游。英雄从城市 sis_i 出发,经过若干个城市,到城市 tit_i 结束,需要特别注意的是,每个英雄的巡游的 sis_i 可以和 tit_i 相同,但是必须至少途径 22 个城市。 每次游行你的花费将由 33 部分构成:

  1. 每个英雄游行经过的距离之和,需要特别注意的是,假如一条边被途径了 kk 次,那么它对答案的贡献是 k×cik\times c_icic_i表示这条边的边权。
  2. 如果一个英雄的巡游的 sis_i 不等于 tit_i,那么会额外增加 CC 的费用。因为英雄要打的回到起点。
  3. 如果一个城市没有任何一个英雄途经,那么这个城市会很不高兴,需要 CC 费用的补偿。

你有无数个的英雄。你要合理安排游行方案,使得费用最小。

由于每年,CC 值都是不一样的。所以你要回答 QQ 个询问,每个询问都是,当 CC 为当前输入数值的时候的答案。

输入格式

第一行正整数 N,M,QN,M,Q

接下来的 MM 行,每行 ai,bi,cia_i,b_i,c_i,表示有一条从 aia_ibib_i,边权为 cic_i 的有向道路。保证不会有自环,但不保证没有重边。

接下来 QQ 行,每行一个 CC,表示询问当每次费用为 CC 时的最小答案。

输出格式

QQ 行,每行代表一个询问的答案。

6 5 3
1 3 2
2 3 2
3 4 2
4 5 2
4 6 2
1
5
10
6
21
32

数据规模与约定

对于 100%100\% 的数据,$2\le N\le 250,1\le M\le 30000,1\le Q\le 10000,1\le ci\le 10000,1\le C\le 10000$。

提示

第一年的时候,CC 只有 11。我们比较懒所以就不安排英雄出游了,需要支付 66 的费用。

第二年的时候,我们可以这么安排:第一个英雄 13451\to 3\to 4\to 5,需要付 2+2+2=62+2+2=6 的费用,同时还要花 55 费用打的回家。再花 5+55+5 的费用来补偿 22 号城市和 66 号城市。

第三年略。