题意：

有n个城市，每个城市与另一个城市之间都有路，需要从一个城市到另一个城市需要$t_{xy}$的时间，一个人到从第一个城市开始视察每一个城市，到每个城市都有一个deadline，到达这个城市的时间不能超过这个deadline，问最小的到达每个城市的到达时间的总和为多少。（n<=30）

思路：

先用floyd处理出每两个点之间的最短路。

n<=30本来肯定是会超时的，可以考虑剪枝。

搜索的常用剪枝：可行性剪枝、最优性剪枝、记忆化搜索、搜索顺序剪枝。

可行性剪枝： 如果当前条件不合法就不再继续搜索，直接return。

最优性剪枝： 如果当前条件所创造出的答案必定比之前的答案大，那么剩下的搜索就毫无必要，甚至可以剪掉。我们利用某个函数估计出此时条件下答案的“下界”，将它与已经推出的答案相比，如果不比当前答案小，就可以剪掉。

一般实现：在搜索取和最大值时，如果后面的全部取最大仍然不比当前答案大就可以返回。
在搜和最小时同理，可以预处理后缀最大/最小和进行快速查询。

搜索顺序剪枝： 在一些迷宫题，网格题，或者其他搜索中可以贪心的题，搜索顺序显得十分重要。我经常听见有人说(我自己也说过)：“从左边搜会T，从右边搜就A了”之类的语句。其实在迷宫、网格类的题目中，以左上->右下为例，右下左上就明显比左上右下优秀。在一些推断搜索题中，从已知信息最多的地方开始搜索显然更加优秀。在一些题中，先搜某个值大的，再搜某个值小的(比如树的度数，产生答案的预计(A*))，速度明显会比乱搜更快。搜索的复杂度明显讲不清，这种剪枝自然是能加就加。

这道题中，

可行性剪枝：在下一个可以走的点里遍历，如果存在$cur+dis[id][i]>d[i]$那就说明那个i是怎么都不能走到的，可以剪掉。

最优性剪枝：如果当前的tot大于现有的ans的话，就可以剪掉。这里对于tot的处理也有讲究，比如到三个点的花费的时间分别是1,3,5，这里到达时间时间相当于是1,1+3,1+3+5，答案是1+1+3+1+3+5，这里可以直接$1*3+3*2+5*1$，把后面的预先加上，这会更快到达要剪枝的条件。

代码：

int dis[35][35];
int d[35];
bool vis[35];
int n,ans;
void dfs(int id,int cur,int tot,int num)//当前时间/累加的答案/经过了几个点
{
    if(tot>=ans)return;//当前累积的tot>=ans就return
    for(int i=2;i<=n;i++)
        if(!vis[i]&&cur+dis[id][i]>d[i])return;//当前的时间+T>任意一个节点的d[i]就return（注意！）
    if(num==n)
    {
        ans=min(ans,tot);
        return;
    }
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(i,cur+dis[id][i],tot+dis[id][i]*(n-num),num+1);//提前把所有之后的都加上（注意！）
            vis[i]=0;
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            scanf("%d",&dis[i][j]);
        for(int i=2;i<=n;i++)
            scanf("%d",&d[i]);
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        ans=INF;
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        dfs(1,0,0,1);
        if(ans==INF)printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}