提交记录

标签有记忆化搜索，但题解好像没人写记忆化搜索。

#include<bits/stdc++.h>
using namespace std;
int a,b,l,r,tot,head[200002],u,v,w;
int sum[200002][202];
bool bj[200002];
struct node{
	int nex,to,w;
}bian[200002];
inline void add(int x,int y,int z)
{
	bian[++tot].to=y;
	bian[tot].nex=head[x];
	bian[tot].w=z;
	head[x]=tot;
	return;
}
inline int dfs(int n,int m,int t,int s)
{
	if(t>100)
	{
		return s;
	}
	if(sum[n][t])
	{
		return (s+sum[n][t]);
	}
	if(n==m)
	{
		return s;
	}
	int su=205;
	for(int i=head[n];i;i=bian[i].nex)
	{
		if(!bj[bian[i].to])
		{
			bj[bian[i].to]=1;
			su=min(su,dfs(bian[i].to,m,t+1,s+bian[i].w/(t+1)));
			bj[bian[i].to]=0;
		}
	}
	sum[n][t]=su;
	return su;
}
int main()
{
	cin>>a>>b>>l>>r;
	for(int i=1;i<=b;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	dfs(r,l,0,0);
	cout<<sum[r][0];
	return 0;
}