bzoj#P3691. 游行
游行
题目描述
每年春季,在某岛屿上都会举行游行活动。
在这个岛屿上有 个城市, 条连接着城市的有向道路。
你要安排英雄们的巡游。英雄从城市 出发,经过若干个城市,到城市 结束,需要特别注意的是,每个英雄的巡游的 可以和 相同,但是必须至少途径 个城市。 每次游行你的花费将由 部分构成:
- 每个英雄游行经过的距离之和,需要特别注意的是,假如一条边被途径了 次,那么它对答案的贡献是 ,表示这条边的边权。
- 如果一个英雄的巡游的 不等于 ,那么会额外增加 的费用。因为英雄要打的回到起点。
- 如果一个城市没有任何一个英雄途经,那么这个城市会很不高兴,需要 费用的补偿。
你有无数个的英雄。你要合理安排游行方案,使得费用最小。
由于每年, 值都是不一样的。所以你要回答 个询问,每个询问都是,当 为当前输入数值的时候的答案。
输入格式
第一行正整数 ;
接下来的 行,每行 ,表示有一条从 到 ,边权为 的有向道路。保证不会有自环,但不保证没有重边。
接下来 行,每行一个 ,表示询问当每次费用为 时的最小答案。
输出格式
行,每行代表一个询问的答案。
6 5 3
1 3 2
2 3 2
3 4 2
4 5 2
4 6 2
1
5
10
6
21
32
数据规模与约定
对于 的数据,$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$。
提示
第一年的时候, 只有 。我们比较懒所以就不安排英雄出游了,需要支付 的费用。
第二年的时候,我们可以这么安排:第一个英雄 ,需要付 的费用,同时还要花 费用打的回家。再花 的费用来补偿 号城市和 号城市。
第三年略。