HDU-4848 Wow! Such Conquering! （回溯+剪枝）

# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;
# define LL long long
const int INF=1<<30;
int mp[35][35],n,a[35],ans,vis[35];
void floyd()
{
    for(int k=0;k<n;++k)
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
void dfs(int cur,int time,int att,int num)
{
    if(num==n){
        ans=min(ans,att);
        return ;
    }
    if(att+(n-num)*time>=ans)
        return ;
    for(int i=1;i<n;++i)
        if(!vis[i]&&time+mp[cur][i]>a[i])
            return ;
    for(int i=1;i<n;++i){
        if(vis[i])
            continue;
        vis[i]=1;
        dfs(i,time+mp[cur][i],att+time+mp[cur][i],num+1);
        vis[i]=0;
    }
}
int main()
{
    while(~scanf("%d",&n))///在这里如果用“!=EOF”会超时。
    {
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                scanf("%d",&mp[i][j]);
        floyd();
        a[0]=0;
        for(int i=1;i<n;++i)
            scanf("%d",a+i);
        memset(vis,0,sizeof(vis));
        ans=INF;
        vis[0]=1;
        dfs(0,0,0,1);
        if(ans!=INF)
            printf("%d\n",ans);
        else
            printf("-1\n");
    }
    return 0;
}