记录编号	24107	评测结果	AAAAATTTTT
题目名称	[RQNOJ 184] 洞窟探索	最终得分	50
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	5.390 s
提交时间	2011-03-28 16:35:05	内存使用	11.83 MiB

#include <cstdio>
#include <queue>
using namespace std;
const int MAXN=1505,MAXM=1005;
const int oo=0x7fffffff/2;

struct Node
{
	int v,w;
	Node *next;
	Node (int _v,int _w,Node *_next):
		v(_v),w(_w),next(_next){}
}*adj[MAXN];

inline void addedge(int u,int v,int w)
{
	adj[u]=new Node(v,w,adj[u]);
	adj[v]=new Node(u,w,adj[v]);
}

int c[MAXN][2],w[MAXN][2];
bool vis[MAXN];
void bfs()
{
	queue<int> q;
	q.push(1);
	vis[1]=true;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(Node *p=adj[u];p;p=p->next)
			if (!vis[p->v])
			{
				vis[p->v]=true;
				if (c[u][0]==0)
				{
					c[u][0]=p->v;
					w[u][0]=p->w;
				}
				else 
				{
					c[u][1]=p->v;
					w[u][1]=p->w;
				}
				q.push(p->v);
			}
	}
}

int N,M;
long long d[MAXN][MAXM];
void dp(int u)
{
	if (u==0)
		return ;	
	for(int i=2;i<=M;i++)
		d[u][i]=oo;
	dp(c[u][0]);
	dp(c[u][1]);
	for(int i=2;i<=M;i++)
		for(int j=0;j<i;j++)
		{
			long long t=d[c[u][0]][j]+d[c[u][1]][i-j-1]+w[u][0]*j*(M-j)+w[u][1]*(i-j-1)*(M-i+j+1);
			if (t<d[u][i])
				d[u][i]=t;
		}
}

int main()
{
	freopen("hole.in","r",stdin);
	freopen("hole.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=0;i<N-1;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
	}
	bfs();
	for(int i=1;i<=M;i++)
		d[0][i]=oo;	
	dp(1);
	printf("%.2f\n",double(d[1][M])/(M*(M-1)/2));
	return 0;
}