<div class="post_brief"><p>
记得这是高一的时候ty同学和我说的东西了。然后现在才解决，可以打败上帝造题的七分钟，荣登解决时间最长的题目了。</p>

 

其实也就是一个高斯消元，用电势来列方程。不过高斯消元写得不熟，平时有空都写ds的题去了。以后不能再这样了。

 

用自己的代码高亮脚本了，虽然还不完善不过还是很开心的。

 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;


const int maxn = 109;
const double inf = 1e100;
const double eps = 1e-8;


double x[maxn], a[maxn][maxn], b[maxn][maxn];
int n, m, perm[maxn];


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


srand(19970911);
while (scanf("%d%d", &amp;n, &amp;m) != EOF) {
	for (int i = 1; i &lt;= n; ++ i)
		perm[i] = i;
	if (n &gt; 2)
		random_shuffle(perm + 2, perm + n);
	for (int i = 1; i &lt;= n; ++ i)
		for (int j = 1; j &lt;= n; ++ j)
			if (i == j)
				a[i][j] = 0;
			else
				a[i][j] = inf;
	while (m --) {
		int u, v;
		double p;
		scanf("%d%d%lf", &amp;u, &amp;v, &amp;p);
		u = perm[u];
		v = perm[v];
		if (u == v)
			continue;
		a[u][v] = 1.0 / (1.0 / a[u][v] + 1.0 / p);
		a[v][u] = a[u][v];
	}
	b[1][1] = 1;
	for (int i = 2; i &lt;= n; ++ i)
		b[1][i] = 0;
	b[1][n + 1] = 0;
	for (int i = 2; i &lt;= n; ++ i) {
		double sr(0);
		for (int j = 1; j &lt;= n; ++ j)
			if (i != j)
				sr += 1.0 / a[i][j];
		for (int j = 1; j &lt;= n; ++ j)
			if (i == j)
				b[i][j] = - sr;
			else
				b[i][j] = 1.0 / a[i][j];
		if (i == n)
			b[i][n + 1] = -1;
		else
			b[i][n + 1] = 0;
	}
	for (int i = 1; i &lt;= n; ++ i) {
		int j0(i);
		for (int j = i + 1; j &lt;= n; ++ j)
			if (abs(b[j0][i]) &lt; abs(b[j][i]))
				j0 = j;
		if (j0 ^ i)
			for (int j = 1; j &lt;= n + 1; ++ j)
				swap(b[i][j], b[j0][j]);
		for (int j = i + 1; j &lt;= n; ++ j) {
			double rat(b[j][i] / b[i][i]);
			for (int k = 1; k &lt;= n + 1; ++ k)
				b[j][k] -= b[i][k] * rat;
		}
	}
	printf("%.2lf\n", b[n][n + 1] / b[n][n]);
}



}