题目描述

saffah所在的国家一共有N个城市，通过N条双向道路连接，使得城市之间两两可以到达。第i条道路连接了A[i]与B[i]，其长度为L[i] km。 这些道路分为M个等级。第i条道路的等级为X[i]。在第j级道路上行驶，你的限速是V[j] km/h，并且每行驶1小时会收取W[j]元的费用。根据道路分级的意义，V[j]与W[j]都随着j单调变化，即对于1 ≤ j < M，满足V[j] > V[j+1], W[j] > W[j+1]。 现在有Q辆货车需要运送货物。第k辆货车要从S[k]前往T[k]，并且其最大速度为U[k] km/h。你需要对每辆货车求出其最小运送花费。

输入格式

第一行三个整数N, M, Q。 接下来N行，每行四个整数A[i], B[i], L[i], X[i]，描述了一条道路。 接下来M行，每行两个整数V[j], W[j]，描述了一个道路等级的限速和费用。 接下来Q行，每行三个整数S[k], T[k], U[k]，描述了一辆货车。

输出格式

输出Q行，即每辆货车的最小运送花费。 你可以输出任意多位的实数，只要与标准答案的相对或绝对误差不超过0.0001就算正确。

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 ≤ N,M,Q ≤ 100,000, 1 ≤ A[i],B[i],S[k],T[k] ≤ N, 1 ≤ X[i] ≤ M, 1 ≤ L[i],V[j],W[j],U[k] ≤ 500,000。 样例解释： 第一辆货车应该沿1→2→3→4行驶，共在1级道路上行驶1.5小时，收费30元。 第二辆货车应该沿1→3→4行驶，在2级道路上行驶5小时，在1级道路上行驶5小时，收费150元。 请不要提交，未加SPJ。

题目来源

By saffah