#P3641. 货车运输

    ID: 2835 传统题 2000ms 256MiB 尝试: 320 已通过: 49 难度: 7 上传者: 标签>难度分类提高+/省选-图论基环树数据结构普通并查集离线与分治查询排序扫描中维护贡献树算法子树转区间差分树状数组LCA树上倍增CF2300

货车运输

货车运输

题目描述

某国有 NN 个城市和 NN 条双向道路,任意两座城市互相可达。第 ii 条道路连接城市 AiA_i 与 BiB_i,长度为 LiL_i 千米,等级为 XiX_i。

道路分成 MM 个等级。第 jj 级道路的限速为 VjV_j 千米/小时,每在这一级道路上行驶一小时收费 WjW_j 元。随等级编号增大,限速和每小时费用都严格下降:

Vj>Vj+1,Wj>Wj+1(1≤j<M).V_j>V_{j+1},\qquad W_j>W_{j+1}\quad (1\le j<M).

有 QQ 辆货车。第 kk 辆要从 SkS_k 开到 TkT_k,车辆本身的最高速度为 UkU_k 千米/小时。求每辆车能达到的最小总花费。行驶中既要遵守道路限速,也不能超过车辆的最高速度,费用按实际在路上行驶的时间计算。同一对城市之间可以有多条道路,各条道路分别计入输入。

输入格式

第一行三个整数 N,M,QN,M,Q。

接下来 NN 行,每行四个整数 Ai,Bi,Li,XiA_i,B_i,L_i,X_i,描述一条道路。

接下来 MM 行,每行两个整数 Vj,WjV_j,W_j,依次描述各等级的限速和收费。

接下来 QQ 行,每行三个整数 Sk,Tk,UkS_k,T_k,U_k,描述一辆货车。

输出格式

输出 QQ 行,每行一个实数,为对应货车的最小总花费。与参考答案的绝对误差或相对误差不超过 10−410^{-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→41\to2\to3\to4 行驶,在 11 级道路上共行驶 1.51.5 小时,花费 3030 元。

第二辆货车可以沿 1→3→41\to3\to4 行驶,在 22 级和 11 级道路上各行驶 55 小时,花费 150150 元。

数据范围

1≤N,M,Q≤1051\le N,M,Q\le 10^5,1≤Ai,Bi,Sk,Tk≤N1\le A_i,B_i,S_k,T_k\le N,1≤Xi≤M1\le X_i\le M,1≤Li,Vj,Wj,Uk≤5000001\le L_i,V_j,W_j,U_k\le 500000。