题意:求K个机器人从同一点出发，遍历所有点所需的最小花费
链接:点我
Sample Input
3 1 1 //3个点，从1出发，1个机器人
1 2 1
1 3 1
3 1 2
1 2 1
1 3 1
Sample Output
3
2
转移方程： dp[i][j]=min(dp[i][j],dp[i][j*k],dp[son[i]][k]+len(i,son[i])*k)
方程还是比较好写的，主要是要遍历所有的点
下面我们分析一下第一个样例
1
/ ＼
/ ＼
2 ３
我们派了一个机器人去3，那么1这一点就没有机器人了，既然需要遍历所有的点，则需要1->2已经走过，即从1出发，然后又返回了1，这时候没有机器人也可以访问完下面的点
那么dp[i][0]表示的就是一个机器人从i点出发，走一条路然后返回到i的值，则我们在递推j的时候，每次先加上这个值，即可以保证所有路都走过一遍
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int dp[MAXN][],val[MAXN],head[MAXN];
int n,m,tt,tot;
struct Edge
{
int to,next,val;
}edge[MAXN*];
void addedge(int u,int v,int w)
{
edge[tot].to=v;
edge[tot].next=head[u];
edge[tot].val=w;
head[u]=tot++;
}
void init()
{
memset(head,-,sizeof(head));
tot=;
memset(dp,,sizeof(dp));
}
void dfs(int u,int pre)
{
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre) continue;
dfs(v,u);
for(int j=m;j>=;j--)
{
dp[u][j]+=dp[v][]+*edge[i].val;
for(int k=;j-k>=;k++)
{
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+k*edge[i].val);
}
}
}
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int st;
int a,b,val;
while(scanf("%d%d%d",&n,&st,&m)!=EOF)
{
init();
for(i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&val);
addedge(a,b,val);
addedge(b,a,val);
}
dfs(st,-);
printf("%d\n",dp[st][m]);
}
}