http://acm.hdu.edu.cn/showproblem.php?pid=4848

比赛的时候我甚至没看这道题，事实上不难....

可是说实话，如今对题意还是理解不太好......

犯的错误：

1、floy循环次序写错，

2、搜索的时候。应该先推断i是不是能够搜（就是可不可能产生解）。然后标记vis[i]=1。我二逼的先标记vis[i]=1，然后推断i是不是可搜，这样肯定会导致有些时候，cnt!=n

我的剪枝方法（2546MS AC）：

搜下一个结点之前。确保时间小于全部的未訪问的结点的Deadline

//#pragma comment(linker, "/STACK:102400000,102400000")

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <iomanip>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const ll ll_INF = ((ull)(-1))>>1;

const double EPS = 1e-8;

const int INF = 1e9+7;

const int MAXN = 50;

int n;

int mat[MAXN][MAXN];

int dis[MAXN][MAXN];

int dead[MAXN];

void floy()

{

    repe(k,1,n)

    for(int i=1;i<=n;i++)

        repe(j,1,n)

                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

}

int ans;

int vis[MAXN];

void dfs(int u, int t, int cnt,int tmp)

{

    if(dead[u]<t || tmp>ans)return;

    if(cnt == n)

    {

        ans=min(ans,tmp);

        return;

    }

    for(int i=2;i<=n;i++)

        if(!vis[i] && dead[i]>=t+dis[u][i])

        {

            int flag=0;

            for(int j=2;j<=n;j++)

                if(!vis[j] && t+dis[u][i]>dead[j] && i!=j)

                        flag=1;

            if(flag)continue;

            vis[i]=1;

            dfs(i,t+dis[u][i],cnt+1,tmp+dis[u][i]*(n-cnt));

            vis[i]=0;

        }

}

int main()

{

    //IN("hdu4848.txt");

    while(~scanf("%d",&n))

    {

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                scanf("%d",&mat[i][j]),dis[i][j]=mat[i][j];

        floy();

        dead[1]=INF;

        repe(i,2,n)

            scanf("%d",&dead[i]);

        ans=INF;

        CL(vis,0);

        vis[1]=1;

        dfs(1,0,1,0);

        if(ans == INF)printf("-1\n");

        else printf("%d\n",ans);

    }

    return 0;

}

网上的方法：（359ms AC）

事实上剪枝思路跟我一样，可是比我的更好

倘若搜到当前结点，检查全部的未訪问的结点，假设不管以哪个未訪问结点为起点都不可能得到解，直接返回，相当于比我少遍历一层并且少了非常多反复

//#pragma comment(linker, "/STACK:102400000,102400000")

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <iomanip>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const ll ll_INF = ((ull)(-1))>>1;

const double EPS = 1e-8;

const int INF = 1e9+7;

const int MAXN = 50;

int n;

int mat[MAXN][MAXN];

int dis[MAXN][MAXN];

int dead[MAXN];

void floy()

{

    repe(k,1,n)

    for(int i=1;i<=n;i++)

        repe(j,1,n)

                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

}

int ans;

int vis[MAXN];

void dfs(int u, int t, int cnt,int tmp)

{

    if(dead[u]<t || tmp>ans)return;

    if(cnt == n)

    {

        ans=min(ans,tmp);

        return;

    }

    for(int i=2;i<=n;i++)

        if(!vis[i] && t+dis[u][i]>dead[i])

            return;

    for(int i=2;i<=n;i++)

        if(!vis[i] && dead[i]>=t+dis[u][i])

        {

            vis[i]=1;

            dfs(i,t+dis[u][i],cnt+1,tmp+dis[u][i]*(n-cnt));

            vis[i]=0;

        }

}

int main()

{

    //IN("hdu4848.txt");

    while(~scanf("%d",&n))

    {

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                scanf("%d",&mat[i][j]),dis[i][j]=mat[i][j];

        floy();

        dead[1]=INF;

        repe(i,2,n)

            scanf("%d",&dead[i]);

        ans=INF;

        CL(vis,0);

        vis[1]=1;

        dfs(1,0,1,0);

        if(ans == INF)printf("-1\n");

        else printf("%d\n",ans);

    }

    return 0;

}