咋办啊，自己的位运算是一点都不会啊，只好康康同机房大佬的代码再让大佬给我讲了
Code：
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\n", ans); 63 return 0; 64 }
不行，得加油了！