等效电阻

题目描述

给你一张电路图，有 $n$ 个顶点和 $m$ 条边，顶点编号从 $1$ 到 $n$。$1$ 号顶点为正极，$n$ 号顶点为负极，电路图保证连通。

边 $(i, j, c)$ 表示第 $i$ 号顶点和第 $j$ 号顶点间存在一条电路，中间有一个电阻值为 $c$ 的电阻，两个顶点之间可能有多个并联电阻线路。

现在问你对于整个电路，从 $1$ 号点到 $n$ 号点的等效电阻为多少。

输入格式

第一行两个正整数 $n$ 和 $m$，表示顶点数和边数。

接下来 $m$ 行，每行三个整数 $i, j, c$，表示 $i$ 号顶点和 $j$ 号顶点中间有一个电阻为 $c$ 的通路。

数据保证顶点 $1$ 和顶点 $n$ 连通。

输出格式

输出一行一个数表示答案。

只要你的答案和标准答案相对误差或者绝对误差在 $10^{-6}$ 以内就算通过。

样例输入 1

3 3
1 2 1
1 2 1
2 3 2

样例输出 1

2.5000000000

样例输入 2

4 5
1 2 1
2 4 4
1 3 8
3 4 19
2 3 12

样例输出 2

4.2098138748

数据范围

对于 $100\%$ 的数据，保证 $2\leq n\leq 50, 1\leq m\leq 2000, 1\leq i, j\leq n, i\neq j, 1\leq c\leq 10^4$。

提示

串联电路: $R = R_1 + R_2 + ... + R_n$

并联电路：$1 / R = 1 / R_1 + 1 / R_2 + ... + 1 / R_n$

$I_{i,j} = U_{i,j} / R_{i,j}$

除了正负极外顶点，有 $I_{in} = I_{out}$

等效电阻 $R_{1, n} = U_{1, n} / I$