题目链接：点击打开链接
题意：从起点出发访问所有的点最后回到出发点，每个点可以多次经过，问最小时间花费。
思路：由于每个点可以多次经过，所以可以考虑先用floyd算法求出最短路，然后进行状压DP，当前访问过的点压缩成二进制状态，每个位代表一个点，1表示访问过，0表示未访问过，dp[state][v]，表示在state状态下，且最后一个访问到的点为v时的最小时间花费。由于起点编号为0，其他点从1到n编号，所以状态压缩时，第i位表示第i + 1个点。
// POJ 3311 Hie with the Pie.cpp 运行/限制：0ms/2000ms #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define INF 0x3f3f3f3f int n; int dist[15][15]; int dp[1 << 12][15]; void floyd() {//多源最短路 for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { for (int t = 0; t <= n; t++) { if (dist[j][t] > dist[j][i] + dist[i][t]) { dist[j][t] = dist[j][i] + dist[i][t]; } } } } } int main(){ while (scanf("%d", &n) != EOF && n) { for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { scanf("%d", &dist[i][j]); } } floyd(); memset(dp, INF, sizeof(dp)); int upper = (1 << n) - 1;//状态上限 for (int i = 1; i <= upper; i++) {//状态枚举 for (int j = 0; j < n; j++) {//状态位枚举，第i位代表第i + 1个点 if ((i & (1 << j)) == 0) continue;//状态位为0 if (i == (1 << j)) {//只有一个状态位为1 dp[i][j] = dist[0][j + 1]; break; } for (int t = 0; t < n; t++) {//多个状态位为1，则枚举前一个被访问的点 if ((i & (1 << t)) && t != j) {//注意前后访问的点不能重复（访问和经过不一个含义） dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][t] + dist[t + 1][j + 1]); } } } } int re = INF; for (int i = 0; i < n; i++) { re = min(re, dp[upper][i] + dist[i + 1][0]); } printf("%d\n", re); } return 0; }
