题意
经典问题：TSP。
给出了n个城市，求一条最短的路径，使得经过每个城市一次且仅一次，最后回到起点。
思路
状态压缩DP。分析问题可知道是一个多阶段决策过程，每个阶段“状态”包括了可以用已经走了哪些点，和当前站在哪个点，决策就是接下来走哪个点。
状态表示：dp[二进制位，表示目前已经走过那些点][最后走的点的序号] = 从起点出发走过的最短路程
答案：min{dp[走过全部点的状态][枚举各个可能的最后走的点i] + dis(i,起点)}
边界：dp[0][起点] = 0,其它都是INF
状态转移：用dp[S][i] + dis(i,j) 去尝试更新dp[S|j][j]
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; int n; long long dis[12][12]; long long dp[12][4096]; void floyd_warshall(){ for (int k = 0; k <=n;k++) { for(int i = 0; i<= n; i++){ for(int j = 0; j<=n ;j++){ if(dis[i][k] + dis[k][j] < dis[i][j]){ dis[i][j] = dis[i][k] + dis[k][j]; } } } } } long long solve(){ memset(dp, 0x3f, sizeof(dp)); for(int i = 0; i < (1 << n) ;i++){ int cnt = 0,lst = 0; for(int j = 1; j <= n; j++){ if(i & (1 << (j-1))){ cnt++; lst = j; } } if(cnt <= 1){ dp[lst][i] = dis[0][lst]; }else{ for(int j = 1; j <= n; j++){ if(i & (1 << (j-1))){ for(int k = 1; k <= n; k++){ if(j != k && i & (1 << (k-1))){ dp[j][i] = min(dp[j][i],dp[k][i^(1 << (j-1))] + dis[k][j]); } } } } } } long long ret = 0x3f3f3f3f3f3f3f3f; for(int i = 1; i<=n;i++){ ret = min(ret,dp[i][(1 << n)-1] + dis[i][0]); } return ret; } int main(){ //freopen("testdata.in", "r", stdin); while(scanf(" %d",&n) != EOF && n){ for(int i = 0; i <= n ;i++){ for(int j =0;j <= n; j++){ scanf(" %lld",&dis[i][j]); } } floyd_warshall(); printf("%lld\n",solve()); } return 0; } |
