全部回复 共 3 条

1. Papyrus在审判你 #1 · 2022-08-17

   SB

2. 许熠谦 #2 · 2022-09-11

   include<bits/stdc++.h>

   using namespace std; const int N = 20;

   int weights[N][N]; int f[1<<N][N];

   // f[i][j]被经过的点以1表示组成的二进制数,并且此时处于点j时的最短路径 // 则题目要求的最短路径就是f[(1<<n)-1][n-1],即所有点都经过了,并且此时处于最后一个点 // 题目要求每一个点能并且只能经过一次. int hamilton(int n){ // memset是把这个段区间的每一个字节置为数c,对于0x3f是一个字节可以表示的最大的有符号的整数. memset(f, 0x3f, sizeof(f));

   f[1][0] = 0;
   // 枚举经过1个2个...n个点的所有可能性
   for(int i = 1; i < (1 << n); ++i){
       for(int j = 0; j < n; ++j){
           if((i >> j) & 1){    //表示当前表示经过点的状态的数i,此时处于点j
               for(int k = 0; k < n; ++k){
                   // 1 ^ (i<<j)表示将上一时刻经过的点j对应的二进制位设置为0
                   // 找出i ^ (1 << j) >> (k & 1)则从上一未经过点j的状态中那些位是1的点k,添加一条点k到点j的路径,看一看是否更短.
                   if(((i ^ (1 << j)) >> k) & 1)
                       f[i][j] = min(f[i][j], f[i^(1 << j)][k]  + weights[k][j]);
               }
           }
       }
   }
   return f[(1 << n) - 1][n-1];
   

   }

   int main(int argc, const char** argv) {

   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   int n;
   cin>>n;
   for(int i = 0; i < n; ++i){
       for(int j = 0; j < n; ++j)
           cin>>weights[i][j];
   }
   cout<<hamilton(n)<<endl;
   return 0;
   

   }

3. ⛴李恒旭⚔♆§ #3 · 2024-07-19

   说3A评论太高级了，不符合房主的气质，说房主是2B还差不多！！！