首页 > 试题广场 >

在一个 个点的完全图中，每条边有边权，牛牛从某一点出发，想要

[单选题]
在一个 个点的完全图中，每条边有边权，牛牛从某一点出发，想要把所有点都访问恰好一遍，想要求最短路径。
我们可以设 dp[s][i] 表示已经走过的点的集合为 s，当前正在第 i 个点。其中 s 的二进制位从右向左数的第 x 位表示是否走过了这一个点，对应位置为 1 表示走过这一点，否则为 0。现在牛牛从第 i 个点出发向第 j 个点移动，若用 dis 表示 i,j 两点间的距离，则下列四个状态转移方程错误的是（）

注意：| 表示二进制中的按位或运算，^ 表示二进制中的按位异或运算，& 表示二进制中的按位与运算。 
  • dp[s+(1 << j)][j] = min(dp[s+(1 << j)][j], dp[s][j] + dis)
  • dp[s | (1 << j)][j] = min(dp[s | (1 << j)][j], dp[s][j] + dis)
  • dp[s ^ (1 << j)][j] = min(dp[s ^ (1 << j)][j], dp[s][j] + dis)
  • dp[s & (1 << j)][j] = min(dp[s & (1 << j)][j], dp[s][j] + dis)
查看正确选项
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

来自：2024秋招-字节跳动...
难度：
0条回答 103浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号