求助
查看原帖
求助
393811
大海中的孤帆楼主2023/8/1 09:07

用最短路和递归做的,递归函数有问题,但不清楚问题在哪,求大佬帮忙看看

#include<bits/stdc++.h>
using namespace std;
int t,n;
int w[1010],v[1010],f[1010][1010];
int y[1010];
double s,sp[1010][1010];
int qm(int a,int b)//min函数
{
	if(a<b)
		return a;
	return 0;
}
double qwq(int i,int j)//递归
{
	if(i==n-1)
		return s/sp[i][j];
	double k=1e9;
	while(f[i][j])
	{
		//cout<<k<<" "<<s<<" "<<sp[i][j]<<" "<<s/sp[i][j]<<endl;
		k=qm(k,s/sp[i][j]+qwq(j+1,j+1));
		j++;
	}
	return k;
}
int main()
{
	cin>>t>>s>>n;
	s*=60;
	for(int i=0;i<n;++i)
	{
		cin>>w[i]>>v[i];
		y[i]=1e9;
	}
	for(int i=0;i<=n;++i)
	{
		for(int j=0;j<=n;++j)
		{
			f[i][j]=1e9;
		}
		f[i][i]=w[i];
		sp[i][i]=v[i];
	}
	for(int i=0;i<n;++i)//数据初始化,能合并的可能性排列完整
	{
		for(int j=i;j<n;++j)
		{
			if(i==j)
				continue;
			if(f[i][j]==0)
				break;
			if(f[i][j-1]+w[j]<=t)
			{
				f[i][j]=f[i][j-1]+w[j];
				sp[i][j]=qm(sp[i][j-1],v[j]);
			}
		}
	}
	printf("%.1lf",qwq(0,0));
	return 0;
	/*for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			printf("%6d ",f[i][j]);
		}
		cout<<endl;
	}
	cout<<endl<<endl;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			cout<<sp[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
	*/
}
2023/8/1 09:07
加载中...