Description:

There are n Doge Planets in the Doge Space. The conqueror of Doge Space is Super Doge, who is going to inspect his Doge Army on all Doge Planets. The inspection starts from Doge Planet 1 where DOS (Doge Olympic Statue) was built. It takes Super Doge exactly Txy time to travel from Doge Planet x to Doge Planet y.
With the ambition of conquering other spaces, he would like to visit all Doge Planets as soon as possible. More specifically, he would like to visit the Doge Planet x at the time no later than Deadlinex. He also wants the sum of all arrival time of each Doge Planet to be as small as possible. You can assume it takes so little time to inspect his Doge Army that we can ignore it.

Input:

There are multiple test cases. Please process till EOF.
Each test case contains several lines. The first line of each test case contains one integer: n, as mentioned above, the number of Doge Planets. Then follow n lines, each contains n integers, where the y-th integer in the x-th line is Txy . Then follows a single line containing n - 1 integers: Deadline2 to Deadlinen.
All numbers are guaranteed to be non-negative integers smaller than or equal to one million. n is guaranteed to be no less than 3 and no more than 30.

Output:

If some Deadlines can not be fulfilled, please output “-1” (which means the Super Doge will say “WOW! So Slow! Such delay! Much Anger! . . . ” , but you do not need to output it), else output the minimum sum of all arrival time to each Doge Planet.

Sample Input:

4
0 3 8 6
4 0 7 4
7 5 0 2
6 9 3 0
30 8 30
4
0 2 3 3
2 0 3 3
2 3 0 3
2 3 3 0
2 3 3

Sample Output:

36
-1

Hint:

Explanation:

In case #1: The Super Doge travels to Doge Planet 2 at the time of 8 and to Doge Planet 3 at the time of 12,
then to Doge Planet 4 at the time of 16.
The minimum sum of all arrival time is 36.

题目链接

给出从第一个点出发到其余点所需时间，求满足每个点时间限制要求情况下一条线路途径所有点后所有点到达时间之和的最小值。

由于要搜索所有情况，所以得首先求出任意两点间所需的最短时间，之后进行深度优先搜索，搜索出最佳结果。

在dfs中，需要对已经不是最结果和已经无法满足要求的情况进行剪枝。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 40;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return 0;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}
template <class T>
inline void out(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

int n;
int ans;
int cost[maxn][maxn];
int require[maxn];
bool vis[maxn];

// 求任意两点见所需的最短时间
void Floyd() {
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}
	}
}

void dfs(int now, int cnt, int res, int sum) {
	// 若未达到时间要求限制或已经不是最佳结果，剪枝
	if (res > require[now] || sum > ans) {
		return;
	}
	// 记录最佳结果
	if (cnt == n) {
		ans = min(sum, ans);
		return;
	}
	// 若即使由当前点直接到达任意未访问点都无法满足时间要求，剪枝
	for (int i = 1; i < n; ++i) {
		if (!vis[i] && res + cost[now][i] > require[i]) {
			return;
		}
	}
	for (int i = 1; i < n; ++i) {
		if (!vis[i] && res + cost[now][i] <= require[i]) {
			vis[i] = 1;
			dfs(i, cnt + 1, res + cost[now][i], sum + cost[now][i] * (n - cnt));
			vis[i] = 0;
		}
	}
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	while (read(n)) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				read(cost[i][j]);
			}
		}
		for (int i = 1; i < n; ++i) {
			read(require[i]);
		}
		Floyd();
		mem(vis, 0);
		vis[0] = 1;
		ans = INF;
		dfs(0, 1, 0, 0);
		ans = ans == INF ? -1 : ans;
		print(ans);
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}