#P4814. [CCO2014] 国王格鲁夫

[CCO2014] 国王格鲁夫

题目描述

本题译自 CCO 2014 Day1 T2「King Gruff

狼国王格鲁夫统治着一个居住着可爱的狐狸的繁荣、快乐的领地。对狐狸们来说,不幸的是,他根本不是一个好国王,而且还想让他们的生活过得很惨。

他的国家有 NN 个城市,由 MM 条路连接,第 ii 条路可以让你从城市 XiX_i 走到另一个城市 YiY_i,并且只能往这个方向走,这条路的长度为 LiL_i,关闭费为 CiC_i,可能会有多条道路以相同的方向连接着两个相同的城市。

国王格鲁夫尤其不喜欢住在两个不同城市 AABB 里的狐狸并且想让他们从城市 AA 到城市 BB 很麻烦甚至根本行不通。具体来说,他将选择一个距离 DD,并且同时关闭某些他王国里的路。关闭的条件是,如果这条路是城市 AA 到城市 BB 路径上的一部分且该路径总长不超过 DD。对于每条这样的路,他将用皇家金库里的钱取支付它的关闭费。一个路径包含一个路的序列,除了第一条路外,每条路起点在前一条路的终点,并且可能多次访问同一个城市或走同一条路。

格鲁夫正在纠结选哪个 DD,不管怎样,大一些的 DD 值可以使得他的狐狸子民更加不方便,但是可能花费他更多的钱!因此,他想了 QQ 个不同的值 D1,D2,...,DQD_1,D_2,...,D_Q,对于每一个值,他想知道需要花费多少来满足他的要求。因为你也不喜欢狐狸,你同意帮他写个程序计算最小花费。

输入格式

第一行包括四个由空格分隔的整数 N,M,A,BN,M,A,B,城市数,道路数,开始城市,结束城市。

接下来 MM 行四个空格分隔的整数 Xi,Yi,Li,CiX_i,Y_i,L_i,C_i,表示一条从 XiX_iYiY_i 的长为 LiL_i 的路,它的关闭费为 CiC_i

接下来一行一个数 QQ,表示询问个数。

接下来 QQ 行包含一个数 DiD_i 表示题中所述距离参数。

输出格式

输出包括 QQ 行,表示根据距离参数 Di(1iQ)D_i(1\le i\le Q) 求出的关闭所有必要的路的总花费。

4 5 1 3
1 2 5 1
1 2 8 50
2 3 2 15
3 1 80 1000
3 4 1 1
4
8
6
90
94
16
0
66
1066
4 3 1 2
2 1 1 1
3 4 10000 10000
4 3 10000 10000
1
1000000000
0

提示

王国如下图所示,每条路只标注了长度。

CCO2014D1T2Pic1

如果 D=8D=8,第一、三条路需要被关闭,他们都是从城市 11 到 城市 33 的长为 77 的路径的一部分,总花费 1+15=161+15=16

如果 D=6D=6,不需要关闭任何路,因为没有从城市 11 到城市 33 的路长度小于或等于 66

如果 D=90D=90,前三条路都要被关闭。

如果 D=94D=94,第四条路也要被关闭,因为它在城市 11 到城市 33 的路径上,该路径长度刚好为 9494,路径为依次走第一、三、四、一、三条路。

王国如下图所示

CCOD2T2Pic2

就像你所看到的一样,狐狸已经有麻烦了,因为这里根本没有从城市 11 到城市 22 的路径,因此对于任何 DD 格鲁夫国王都不需要关闭任何道路。

对于至多 20%20\% 的数据,1N5001\le N\le 500

对于至多 20%20\% 的数据,Q=1Q=1

对于至多 80%80\% 的数据,1Q201\le Q\le 20

对于 100%100\% 的数据,1Xi,Yi,A,BN105,1\le X_i,Y_i,A,B\le N \le 10^5, 0M105,0\le M\le 10^5, 1Li,Ci104,1\le L_i,C_i\le 10^4, 1Q105,1\le Q\le 10^5, 1D1091\le D\le 10^9