问题标题: 1048

1
0
已解决
方亦欧
方亦欧
新手光能
新手光能

# include <iostream>
using namespace std;

int n; 
int a[30][30],used[30],min1=10000000;

void dfs(int t,int sum)
{
    for(int i=t;i<=n;i++)
        if(!used[i])
        {
            sum+=a[t][i];
            used[i]=1;
            if(t<n)
                dfs(t+1,sum);
            else if(sum<min1)
                min1=sum;
            sum-=a[t][i];
            used[i]=0;    
        }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    dfs(1,0);
    cout<<min1;
    return 0;
}

为什么超时了两个测试点?


3
已采纳
吴峻逸
吴峻逸
初级守护
初级守护

你要剪枝啊,判断现在累加起来的费用是否已经超过了现在的最小总费用,如果超过就不必再搜了,直接return ;

 

0
我要回答