【题意】给了n个点，对于每个点除了0点之外都有一个到达的deadline，超过了这个期限的话，就不能到达了。并且给出了从u到v点的权值！现在要求从0到达n-1点的最小耗费时间！

【分析】由于只有30个点，点很少Q_Q，所以可以直接预处理出两点之间的最短距离，然后dfs，这里最重要的dfs的两种剪枝，亲身测试，去掉任意一个都会tle！

【剪枝1】这个是针对最后期限的剪枝，如果当前点到达任意一个点将超过ded【i】那么当前往下的搜索就可以不做了！

【剪枝2】如果当前的答案cur_ans+(n-num)*cur_ans>ans，其中ans代表当前最好的决策,num代表已经走过的点数，那么也可以停止搜索！

【AC代码】

#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 32;
const int inf = 1<<30;
int a[maxn],vis[maxn],ded[maxn];
int maze[maxn][maxn];
int ans,n;
void floyd()
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                maze[i][j]=min(maze[i][j],maze[i][k]+maze[k][j]);
}
void dfs(int id,int cur_time,int cur_sum_time,int num)
{
    if(num==n)
    {
        ans=min(ans,cur_sum_time);
        return ;
    }
    //剪枝1
    if(cur_sum_time+(n-num)*cur_time>=ans)
    {
        return ;
    }
    //剪枝2
    for(int i=1; i<n;i++)
    {
        if(!vis[i]&&cur_time+maze[id][i]>ded[i])return ;
    }
    for(int i=1; i<n; i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(i,cur_time+maze[id][i],cur_sum_time+cur_time+maze[id][i],num+1);
            vis[i]=0;
        }
    }
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&maze[i][j]);
        floyd();
        ded[0]=0;
        for(int i=1;i<n;i++)scanf("%d",&ded[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;
}