7级题目答案

全班都进前50的屑  •  2年前


傻了吧,又没答案


Comments:

SB


Papyrus在审判你  •  2年前

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;

}


许熠谦  •  2年前

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


⛴李恒旭⚔♆§  •  8个月前

请先登录,才能进行评论