1 /* 2 ID:esxgx1 3 LANG:C++ 4 PROG:B 5 */ 6 #include <cstdio> 7 #include <iostream> 8 #include <cstring> 9 #include <algorithm>10 using namespace std;11 12 #define INF        0x3f3f3f3f13 14 #define MAXN    3115 int N;16 int dis[MAXN][MAXN];17 int later_time[MAXN];18 19 #define pp        {20     int o = time + dis[i][j];    21     if (sumtime + o*(N - layers) >= mint) continue; 22     if (blk & (1<<j)) {    23         if (layers + 1 >= N) {24             if (mint > sumtime + o) 25                 mint = sumtime + o; 26         } else dfs(layers + 1, blk, sumtime + o, o, j);    27     }    28 }29 30 int mint;31 32 void dfs(int layers, int blk, int sumtime, int time, int i)33 {34     blk ^= 1<<i;35     for(int j=1; j<i; ++j)36         if (blk & (1<<j) && time + dis[i][j] > later_time[j]) return;37     for(int j=i+1; j<N; ++j)38         if (blk & (1<<j) && time + dis[i][j] > later_time[j]) return;39     for(int j=1; j<i; ++j) pp40     for(int j=i+1; j<N; ++j) pp41 }42 43 int main(void)44 {45     #ifndef ONLINE_JUDGE46     freopen("in.txt", "r", stdin);47     #endif48     while(scanf("%d", &N) > 0) {49         //memset(blk, 0, sizeof(blk));50         for(int i=0; i<N; ++i)51             for(int j=0; j<N; ++j)52                 scanf("%d", &dis[i][j]);53         for(int i=1; i<N; ++i)54             scanf("%d", &later_time[i]);55         for(int k = 0; k<N; ++k)56             for(int i=0; i<N; ++i)57                 if (dis[i][k])58                     for(int j=0; j<N; ++j)59                         if (dis[k][j] && dis[i][j] > dis[i][k] + dis[k][j])60                             dis[i][j] = dis[i][k] + dis[k][j];61         mint = INF;62         dfs(1,~0, 0, 0, 0);63         if (mint >= INF) printf("-1\n");64         else printf("%d\n", mint);65     }66     return 0;67 }