比赛的时候一看,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] 表示要访问第一个国家且没有访问国 …

＿＿＿＿＿＿ 好蠢，竟然没看出来这道题的不同之处，以为就是个搜 然后样例什么的都过了．．． 结果显然wa... 然后才发现，这道题应该是tsp问题． 解法是先跑一遍bfs, 对于所有的脏点和起点，得到没两个点之间的距离． 然后跑一遍dfs，枚举出所有的组合，同时更新答案． 晚安． /************************************************************************* > File Name: code/poj/rr2688.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: …