HDOJ 5418-Victor and World Victor and World Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others) Total Submission(s): 643 Accepted Submission(s): 268 Problem Description After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are n countries on the earth, which are numbered from 1 to n. They are connected by m undirected flights, detailedly the i-th flight connects the ui-th and the vi-th country, and it will cost Victor’s airplane wi L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country. Victor now is at the country whose number is 1, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country. Input The first line of the input contains an integer T, denoting the number of test cases. In every test case, there are two integers n and m in the first line, denoting the number of the countries and the number of the flights. Then there are m lines, each line contains three integers ui, vi and wi, describing a flight. 1≤T≤20. 1≤n≤16. 1≤m≤100000. 1≤wi≤100. 1≤ui,vi≤n. Output Your program should print T lines : the i-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel. Sample Input 1 3 2 1 2 2 1 3 3 Sample Output 10 Source BestCoder Round #52 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5416 5415

---

此题是可重复访问城市的旅行商问题（TSP），即从1号城市开始，经过每个城市至少一次，然后回到1号，问飞机消耗的最少燃料是多少。 根据题解，首先使用Floyd算法求出所有点对的最短路径dis[i][j]，然后DP算法求解。 用一个整数s的二进制表示当前走过城市的状态，第i位为1表示第i个城市已经访问过，为0表示没访问过。dp[s][i]表示当前走过城市状态为s，且最后走过的城市编号为i，即到达了城市i。则有状态转移方程： $$dp[s|(1<<i)][i]=min(dp[s][j]+dis[i][j])$$ 条件为s&(1<<j)!=0且s&(1<<i)==0。 含义为：在s已经访问过j但是没有访问过i的情况下，转移到访问i的状态s|(1<<i)消耗的燃料为所有“s最后访问的是j消耗的燃料dp[s][j]，加上从j走到i消耗的燃料之和”情况中的最小值。 最终结果就是s中所有位为1的状态，再从该状态回到城市1的燃料之和的最小值，即min(dp[(1<<n)-1][i]+dis[i][1])。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int kMaxN = 17, kINF = 0x3f3f3f3f; int dis[kMaxN][kMaxN], dp[1 << kMaxN][kMaxN]; int n, m; void Init() { memset(dis, 0x3f, sizeof(dis)); memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i <= n; i++) dis[i][i] = 0; } void Floyd() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]); } int main() { freopen("input.txt", "r", stdin); int t, u, v, w; scanf("%d", &t); while (t–) { scanf("%d %d", &n, &m); Init(); while (m–) { scanf("%d %d %d", &u, &v, &w); dis[u][v] = min(w, dis[u][v]); dis[v][u] = dis[u][v]; } Floyd(); dp[1][1] = 0; for (int status = 1; status < (1 << n); status++)//枚举状态 { for (int i = 1; i <= n; i++)//枚举最后访问的城市 { //if (status&(1 << (i-1))==0)//(1) if ((status&(1 << (i-1)))==0)//(2)i有没有访问过都可以 { for (int j = 1; j <= n; j++)//枚举中间转折点 { if (status&(1 << (j-1)))//(3)转折点j一定要访问过 dp[status | (1 << (i-1))][i] = min(dp[status | (1 << (i-1))][i], dp[status][j] + dis[i][j]); } } } } int ans = kINF; for (int i = 1; i <= n; i++) ans = min(ans, dp[(1 << n) – 1][i] + dis[i][1]); printf("%d\n", n == 1 ? 0 : ans); } return 0; } [/cpp] 本代码提交AC，用时717MS，内存10284K。 代码中需要注意一点，代码(2)一定不要写成了(1)，要不然WA到死，&的优先级低于==，切记！ 其实(2)处的if可以不要，因为本TSP问题可以重复访问某个城市，所以这里可以不判断下一步需要访问的城市之前有没有访问过，只是加了if能缩短时间；但是(3)处的if判断一定要，因为需要在城市j中转，j之前必须访问过。 另外查看大神的代码，发现很喜欢用0x3f3f3f3f而不是0x7fffffff作为程序中的无穷大，这是有道理的，详情看这篇博客。]]>