货车运输
题目描述
某国有 N 个城市和 N 条双向道路,任意两座城市互相可达。第 i 条道路连接城市 Ai 与 Bi,长度为 Li 千米,等级为 Xi。
道路分成 M 个等级。第 j 级道路的限速为 Vj 千米/小时,每在这一级道路上行驶一小时收费 Wj 元。随等级编号增大,限速和每小时费用都严格下降:
Vj>Vj+1,Wj>Wj+1(1≤j<M).
有 Q 辆货车。第 k 辆要从 Sk 开到 Tk,车辆本身的最高速度为 Uk 千米/小时。求每辆车能达到的最小总花费。行驶中既要遵守道路限速,也不能超过车辆的最高速度,费用按实际在路上行驶的时间计算。同一对城市之间可以有多条道路,各条道路分别计入输入。
输入格式
第一行三个整数 N,M,Q。
接下来 N 行,每行四个整数 Ai,Bi,Li,Xi,描述一条道路。
接下来 M 行,每行两个整数 Vj,Wj,依次描述各等级的限速和收费。
接下来 Q 行,每行三个整数 Sk,Tk,Uk,描述一辆货车。
输出格式
输出 Q 行,每行一个实数,为对应货车的最小总花费。与参考答案的绝对误差或相对误差不超过 10−4 即可。
4 2 2
1 2 50 1
2 3 50 1
1 3 50 2
3 4 50 1
100 20
10 10
1 4 100
1 4 10
30
150
样例解释
第一辆货车可以沿 1→2→3→4 行驶,在 1 级道路上共行驶 1.5 小时,花费 30 元。
第二辆货车可以沿 1→3→4 行驶,在 2 级和 1 级道路上各行驶 5 小时,花费 150 元。
数据范围
1≤N,M,Q≤105,1≤Ai,Bi,Sk,Tk≤N,1≤Xi≤M,1≤Li,Vj,Wj,Uk≤500000。