计算电压

题目背景

相信不少人轻松灭掉 1,2 两题(蒟蒻无视此句) ,我相信,大家对物理也是很有兴趣的(众人:我们对揍人也是很有兴趣的) ,那么,再奉上 100 分给Physicaler 们。

题目描述

现给定一个电阻网络,已知其中每条边上的电阻,和若干个点和负极之间的电压(电源电压不变) ,现在求任意两点之间的电压。

输入输出格式

输入格式


第一行三个数n,m,k,q,表示n个节点(可能是几个点用导线相连接,与一个点等价,编号为1-n,0号节点为电源负极),m个定值电阻,每个定值电阻连接两个点,k表示电源正极有k个接口,有q个询问。 以下k行,每行两整数,表示电源这k个正极的编号与该接线柱与电源负极负极之间的电压Ui。 以下m行,每行三个数,Vi,Wi,Ri,表示Ui与Vi之间添加一条阻值为R的电阻丝。 以下q行,每行两个整数Ai,Bi,表示要求Ai Bi之间的电压。

输出格式


q 行,每行一个实数,保留小数点后两位。(若 A 点电压低于 B 点,输出负值)

输入输出样例

输入样例 #1

3 5 1 3
1 18
1 2 6
1 3 2
2 3 6
3 0 6
2 0 2
1 0
2 3
1 2

输出样例 #1

18.00
-6.00
12.00

说明

【数据范围】 对于10%的数据,q=1; 对于20%的数据,1≤n≤10,保证电路为串联,并联或混联; 对于40%的数据,1≤n≤40,k≤5; 对于100%的数据,1≤k≤n≤200,1≤m≤200,000,1≤Ri,Ui≤10,000,1≤q≤1,000,000. 【限制】 时间限制:2s,内存限制:256M 【注释】 样例如图所示 ![](https://cdn.luogu.org/upload/pic/722.png)