C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 620K, 提交时间: 2020-04-04 08:48:39

#include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
#define maxn 33
#define fi first
#define se second
int n,m;
vector<P>g[maxn];
int sta[maxn];
int vs[maxn];
double ans=1e9;
double pw2(double x)
{
	return x*x;
}
void cal(int l,int r)
{
	double tot=0.0;
	for(int i=l;i<=r;++i)
	tot+=sta[i];
	tot/=(r-l+1);
	double ret=0.0;
	for(int i=l;i<=r;++i)
	ret+=pw2(sta[i]-tot);
	ret/=(r-l+1);
	ans=min(ans,sqrt(ret));
}
void dfs(int u,int d)
{
	vs[u]=d;
	for(auto it:g[u])
	{
		int v=it.fi,w=it.se;
		sta[d]=w;
		if(v==n) cal(1,d);
		if(!vs[v]) dfs(v,d+1);
		else cal(vs[v],d); 
	}
	vs[u]=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back(P(v,w));
	}
	dfs(1,1);
	printf("%.20f\n",ans);
	return 0;
}