题目大意：求一条方差最小的路径，给定起点和中点。
我们先考虑方差的计算公式，可以知道：方差与路径平方和，路径长度，路径段数有关。
由于看起来数据范围较小，我们考虑dp[i=（第几个点）][j=（经过几条边）][k=（边权和）]=该限制下的路径最小平方和。
怎么实现这个dp？
拓扑排序套枚举j,k刚好。
最后的答案一定在dp[n][j][k]里，枚举找最小值即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define maxn 1000000007
#define maxv 55
#define maxe 305
#define maxd 25
using namespace std;
struct edge
{
long long v,w,nxt;
}e[maxe];
long long n,m,g[maxv],dp[maxv][maxd][16005];
long long x,y,z,nume=0,inq[maxv],sum=0;
double ans=127;
void addedge(long long uu,long long vv,long long ww)
{
e[++nume].v=vv;
e[nume].w=ww;
e[nume].nxt=g[uu];
g[uu]=nume;
}
void topu()
{
queue <long long> q;
for (long long i=1;i<=n;i++)
{
if (inq[i]==0)
q.push(i);
}
dp[1][0][0]=0;
while (!q.empty())
{
long long head=q.front();
q.pop();
for (long long j=0;j<=20;j++)
for (long long k=0;k<=sum;k++)
{
if (dp[head][j][k]!=maxn)
{
for (long long i=g[head];i;i=e[i].nxt)
{
long long v=e[i].v,w=e[i].w;
if ((j+1<=20) && (k+w<=sum))
dp[v][j+1][k+w]=min(dp[v][j+1][k+w],dp[head][j][k]+w*w);
}
}
}
for (long long i=g[head];i;i=e[i].nxt)
{
if (!--inq[e[i].v])
q.push(e[i].v);
}
}
}
int main()
{
freopen("library.in","r",stdin);
freopen("library.out","w",stdout);
memset(g,0,sizeof(g));
memset(inq,0,sizeof(inq));
scanf("%lld%lld",&n,&m);
for (long long i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
addedge(x,y,z);
inq[y]++;
sum=sum+z;
}
for (long long i=0;i<=n;i++)
for (long long j=0;j<=20;j++)
for (long long k=0;k<=sum;k++)
dp[i][j][k]=maxn;
topu();
for (long long j=1;j<=20;j++)
for (long long k=0;k<=sum;k++)
ans=min(ans,((double)dp[n][j][k]/(double)j)-(double)(k*k)/(double)(j*j));
printf("%.4f",ans);
return 0;
}
codevs 4438m YJQ runs upstairs
原文：http://www.cnblogs.com/ziliuziliu/p/5061300.html