思路：

首先设f[i][j]表示第1个人走到i点，第二个人走到j点的最小方差。
根据方差化简可以看出只用维护路径和，平方和

c o d e code code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int n, m;
int tot, head[100100];
struct node
{
	int to, next, w;
}b[1000100];
double f[30][60][1060];
double ans=1e9;

void add(int x, int y, int w)
{
	b[++tot]=(node){y, head[x], w};
	head[x]=tot;
}

int main()
{
	freopen("library.in", "r", stdin);
	freopen("library.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(y, x, z);
	}
	for(int i=0; i<=20; i++)
		for(int j=1; j<=n; j++)
			for(int k=0; k<=1030; k++)
				f[i][j][k]=1000000000.0;
	f[0][1][0]=0.0;	
	for(int k=0; k<=1030; k++)
		for(int i=1; i<20; i++)
			for(int j=2; j<=n; j++)
				for(int i1=head[j]; i1; i1=b[i1].next)
				{
					int v=b[i1].to;
					if(k-b[i1].w<0)
						continue;
					f[i][j][k]=min(f[i][j][k], f[i-1][v][k-b[i1].w]+b[i1].w*b[i1].w);
				}
	double ans=1000000000.0;
	for(int i=1; i<20; i++)
	{
		for(int j=0; j<=1030; j++)
		{
			if(f[i][n][j]==1000000000.0)
				continue;
			double sum=abs((f[i][n][j]*1.0/i*1.0)-(j*1.0*j)/(i*1.0*i));
			//cout<<sum<<endl;
			ans=min(ans, sum);
		}
	}
	printf("%.4lf", ans);
	return 0;
}