比赛的时候一看,tsp么 前些天好像刚写过一个clean robot什么的 然后发现n才16,而m很大.. 应该有很多重复的. 那么我们取油费最少的. 然后先做一遍 floyd 之后我写了一个dfs...TLE 了...sad 正解是状压dp 虽然没写过状压dp 但是之前写过一道状态压缩的bfs 所以理解起来没有问题. 这道题的做法是: 用dp[i][j]表示当前访问国家的状态为s,要访问的国家为j的时候的最小费用.i是二进制,i的第p位为1表示第p个国家已经访问过了,否则表示没有访问过. 那么状态转移方程则为:dp[i|(1< 初始化的时候d[i][i] =0,其他为inf dp[0][0] 表示要访问第一个国家且没有访问国 …