HDU 4848

最短路relax + 带剪枝的搜索，个人觉得此剪枝十分牛逼，如果不参照题解我是反应不过来的。
 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        0x3f3f3f3f
13 
14 #define MAXN    31
15 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) pp
40     for(int j=i+1; j<N; ++j) pp
41 }
42 
43 int main(void)
44 {
45     #ifndef ONLINE_JUDGE
46     freopen("in.txt", "r", stdin);
47     #endif
48     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
");
64         else printf("%d
", mint);
65     }
66     return 0;
67 }
2014-07-26 01:36:39
Accepted
4848
265MS
288K
1469 B
G++