网站制作与免费网站建设,网站怎么做地图导航,昆明做网站魄罗科技,天元建设集团有限公司工程最短Hamilton路径 核心思想#xff1a; 数位dp 用二进制数 存当前所有点 遍历过为1 遍历i图中j点 若j点走过 则求j点路径长度 f[state][j] f[state_k][k] w[k][j] state为除去j点的图 #includeiostream#includecstring#includealgorithmusing n…最短Hamilton路径 核心思想 数位dp 用二进制数 存当前所有点 遍历过为1 遍历i图中j点 若j点走过 则求j点路径长度 f[state][j] f[state_k][k] w[k][j] state为除去j点的图 #includeiostream#includecstring#includealgorithmusing namespace std;const int N 20, M 1 N ;int f[M][N];int w[N][N]; //权值int n;int main(){cinn;for(int i0;in;i)for(int j0;jn;j)cinw[i][j]; //输入所有边长度(权值)memset(f , 0x3f, sizeof f); //初始化无穷大 便于取minf[1][0] 0; //只有起点走过 且当前点为起点 距离为0for(int i1;i 1 n;i) //遍历每一张图for(int j0;jn;j) //遍历i图中每个点if(i j 1) // 若j点走过for(int k 0;kn;k) //遍历j点前一个点kif(i k 1) //k也走过 //更新f[i][j] f[去掉i][k] w //特别地 当j k时 f[state][k] 不合法 因为图中必须包含k点//所有min只会取f[i][j]f[i][j] min(f[i][j] , f[i - (1 j)][k] w[k][j]);cout f[(1 n) - 1][n-1]endl; //输出所有点都走过 当前点为n-1的数值}
