UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3691. 游行

Statistics 下载数据

Description

每年春季,在某岛屿上都会举行游行活动。
在这个岛屿上有N个城市,M条连接着城市的有向道路。
你要安排英雄们的巡游。英雄从城市si出发,经过若干个城市,到城市ti结束,需要特别注意的是,每个英雄的巡游的si可以和ti相同,但是必须至少途径2个城市。
每次游行你的花费将由3部分构成:
1.每个英雄游行经过的距离之和,需要特别注意的是,假如一条边被途径了k次,那么它对答案的贡献是k*ci,ci表示这条边的边权。
2.如果一个英雄的巡游的si不等于ti,那么会额外增加C的费用。因为英雄要打的回到起点。
3.如果一个城市没有任何一个英雄途经,那么这个城市会很不高兴,需要C费用的补偿。
你有无数个的英雄。你要合理安排游行方案,使得费用最小。
由于每年,C值都是不一样的。所以你要回答Q个询问,每个询问都是,当C为当前输入数值的时候的答案。

Input

第一行正整数N,M,Q;
接下来的M行,每行ai,bi,ci,表示有一条从ai到bi,边权为ci的有向道路。保证不会有自环,但不保证没有重边。
接下来Q行,每行一个C,表示询问当每次费用为C时的最小答案。

Output

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

Sample Input

6 5 3
1 3 2
2 3 2
3 4 2
4 5 2
4 6 2
1
5
10

Sample Output

6
21
32

Hint

【样例说明】

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

第二年的时候,我们可以这么安排:

第一个英雄1->3->4->5,需要付2+2+2=6的费用,同时还要花5费用打的回家。再花5+5的费用来补偿2号城市和6号城市。

第三年略。


【数据范围】

对于100%的数据,2<=N<=250,1<=M<=30000,1<=Q<=10000。

1<=ci<=10000,1<=C<=10000。


Source