NOIP2017宝藏

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6 + 7;
 4 const int inf = 0x3f3f3f3f;
 5 int n, m;
 6 int G[N];//G[i]表示点i能到达的所有点 
 7 int dp[N][21];//dp[i][k]表示到达i这个状态走k步的花费 
 8 int dis[21][21];//存边 
 9 int main () {
10     scanf("%d%d", &n, &m);
11     memset(dis, 0x3f, sizeof dis);
12     for (int i = 1; i <= m; i++) {
13         int u, v, w;
14         scanf("%d%d%d", &u, &v, &w);
15         u--, v--;//这里--是因为在以后的位运算中会比较方便 
16         dis[u][v] = dis[v][u] = min(dis[u][v], w);//有重边 
17     }
18     int all = (1 << n) - 1;
19     for (int i = 1; i <= all; i++) {//枚举所有状态 
20         for (int j = 0; j < n; j++) {//枚举所有点 
21             if ((1 << j) & i) {//如果状态i包含j 
22                 dis[j][j] = 0;//初始化到自己为0 
23                 for (int k = 0; k < n; k++) {
24                     if (dis[j][k] != inf) {
25                         G[i] |= (1 << k);//标记能到达的所有点 
26                     }
27                 }
28             }
29         }
30     }
31     memset(dp, 0x3f, sizeof dp);
32     for (int i = 0; i < n; i++) {
33         dp[1 << i][0] = 0;//不走的时候花费为0 
34     }
35     for (int i = 2; i <= all; i++) {//枚举所有状态,从2开始时因为1的自己只有自己和空集,不考虑 
36         for (int j = i - 1; j; j = (j - 1) & i) {//枚举i状态的子集 
37             if ((G[j] | i) == G[j]) {//如果j能到达i状态 
38                 int sum = 0;
39                 int rest = j ^ i;//取出剩下没到过的点 
40                 for (int k = 0; k < n; k++) {//枚举所有终点 
41                     if ((1 << k) & rest) {//如果是剩下的没到过的点 
42                         int tmp = inf;
43                         for (int h = 0; h < n; h++) {//枚举起点 
44                             if ((1 << h) & j) {//如果该点在j状态中 
45                                 tmp = min(tmp, dis[h][k]);//更新 
46                             }
47                         }
48                         sum += tmp;//算出从j状态到i状态总最小花费 
49                     }
50                 }
51                 for (int k = 1; k < n; k++) {
52                     if (dp[j][k - 1] == inf) continue;//上一步不能到达就跳过 
53                     dp[i][k] = min(dp[i][k], dp[j][k - 1] + sum * k);//更新 
54                 }
55             }
56         }
57     }
58     int ans = inf;
59     for (int i = 0; i < n; i++) {
60         ans = min(ans, dp[all][i]);//找最小值 
61     }
62     printf("%d
", ans);
63     return 0;
64 }