Rational Resistors

J. Michael Straczynski, "Babylon 5" and "Jeremiah". Given a network of resistors, what is the equivalent resistance between two given points in the network? More precisely, consider an undirected, weighted graph, where each edge is a wire with the edge weight representing its resistance, in Ohms. Given a pair of nodes, A and B, in this graph, imagine passing 1 Ampere of current from A to B. What will be the voltage between A and B, in Volts? A brief review of high school physics. For any pair of points, P and Q, in the network, the voltage between the points is the difference in potentials at the two points (V(P) - V(Q)) and is equal to the current from P to Q times the resistance between P and Q. For any point in the network, the sum of the currents entering the point is zero (conservation of charge). Warning! This problem is harder than it seems. Input The first line of input gives the number of cases, N (N < 30). N test cases follow. Each one starts with a description of a graph: n m (the number of nodes and wires in the graph) n will not be larger than 16. The next m lines contain 3 integers each: uvr specifying that there is a wire with resistance r (0 < r < 10) connecting node u to node v. The nodes are numbered from 0 to n − 1. There can be multiple wires connecting the same pair of nodes and wires connecting a node to itself. The next line of each test case will contain the number of queries, Q (0≤Q≤10). ThenextQlineswilllistpairsofnodesAandB. Output For each test case, output the line ‘Case #x:’, where x is the number of the test case. Then print Q lines of the form ‘Resistance between A and B is s/t’, where s/t is a fraction in lowest terms. Print ‘1/0’ if no current can go from A to B. Finally, print an empty line after each test case. Sample Input 4 32 011 122 2 02 10 22 011 102 1 “Resistance will be punished. Cooperation will be rewarded.”

2/2 01 20 1 01 44 011 122 233 131 1 03 Sample Output Case #1: Resistance between 0 and 2 is 3/1 Resistance between 1 and 0 is 1/1 Case #2: Resistance between 0 and 1 is 2/3 Case #3: Resistance between 0 and 1 is 1/0 Case #4: Resistance between 0 and 3 is 11/6