【题意】：给出一个有向图，n个城市(n<=21)，还有m个限制a b，表示要访问城市b要先访问城市a。求从0号城市出发的最短哈密顿路。

【题解】：经典的状态压缩dp。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 21
22 const int inf = 1000000;
23 int n, m;
24 int dp[maxn][1<<maxn];
25 int maz[maxn][maxn];
26 int limit[maxn];
27 
28 void solve() {
29     for(int i = 0; i < n; i++) 
30         for(int j = 0; j < (1 << n); j++)
31             dp[i][j] = inf;
32     dp[0][1] = 0;
33     for(int mask = 1; mask < (1<<n); mask++)
34         for(int i = 0; i < n; i++)
35             for(int j = 0; j < n; j++)
36                 if((mask & (1<<i)) && !(mask & (1 << j)) && maz[i][j] != -1 && (mask & limit[j]) == limit[j])
37                     dp[j][mask|(1<<j)] = min(dp[j][mask|(1<<j)], dp[i][mask] + maz[i][j]);
38     int ans = inf;
39     for(int i = 0; i < n; i++)
40         ans = min(ans, dp[i][(1<<n)-1]);
41     printf("%d\n", (ans == inf) ? -1 : ans);
42 }
43 
44 int main() {
45     while(~scanf("%d%d", &n, &m)) {
46         memset(limit, 0, sizeof(limit));
47         for(int i = 0; i < n; i++) 
48             for(int j = 0; j < n; j++)
49                 scanf("%d", &maz[i][j]);
50         for(int i = 0; i < m; i++) {
51             int u, v;
52             scanf("%d%d", &u, &v);
53             limit[v] |= (1<<u);
54         }
55         solve();
56     }
57     return 0;
58 }
59