3、笨笨的电路

Grade 0 Open Time Saturday, 22 September 2012, 4:55 pm
Discount 0.8 Time Discount Saturday, 22 September 2012, 4:55 pm
Allow late Yes Close Time Saturday, 22 September 2012, 4:55 pm

  【题目描述】
  笨笨大学的专业是电气信息类,这天他又在家里摆弄电路了。这个电路分为3个部分,最左边是一些杂乱无章的N个点,编号为l-N,其中l号点是输入信号发出点。它们互相之间可以用某长度的电线连接起来,一个结点上可以接多根电线,但是电线不能在非结点处相接,另外,它们还可能与第2部分的点通过电线相连。第2部分是整齐的一竖排M个信号放大器,编号为N+l-N+M。它们互相之间没有连接,但可能与第1部分或第3部分的点相接,如果它们与l号点相连(直接或者间接),则可以输出数字信号l,否则输出0。第3部分的点是T个门电路,编号为N+M+l-N+M+T。每一个门电路有两个输入端,一个输出端,输入端与某个放大器或编号比它小的门电路的输出端相连,(这一部分的连接其实是一个有向无环图。)输出端的值是将两个输入的数字信号进行异或运算得到的结果。编号为N+M+T的点的输出端连接到最后的输出,现在告诉你最终输出结果,以及节点之间可用来连接的电线情况,要求你怎样用最短的电线得到这个最终输出,另外最终输出的门电路即(N+M+T号节点)必须与输入信号发出点(1号节点)连通
  【输入格式】
  第一行四个数N、M、T、W
  W表示第1、2部分点互相之间可以连接的电线总数。(不会有重边和自环)
    接下来W行
    每行3个数,A、B、C。
    代表A,B两点之间可以用一条长度为C的电线连接。
    接下来T行
    每行两个整数X,Y。
    第W+l+i行的两个数表示编号为(N+M)的门电路的两个输入端分别与编号
为X,Y的点输出端相连。(X、Y可能相等)
    最后一行最终输出,用0或l表示。
    【输出格式】
    一行一个整数,表示得到最终输出最小要用的电线长度。
    如果得不到这个输出,则输出一l。
    【样例输入】
    2 6 7 7
    1 2 10
    2 3 2
    2 4 1
    1 5 10
    1 6 10
    1 7 10
    1 8 10
    6 7
    5 7
    9 10
    3 8
    4 8
    12 13
    11 14
    0
    【样例输出】
13
N≤l00
M≤100
T≤5000
W≤12000