题目链接&＃xff1a;http://poj.org/problem?id&＃61;3311
题意&＃xff1a;
你在0号点&＃xff08;pizza店&＃xff09;&＃xff0c;要往1到n号节点送pizza。
每个节点可以重复经过。
给你一个(n&＃43;1)*(n&＃43;1)的邻接矩阵&＃xff0c;表示各点之间距离。
问你送完所有pizza再返回店里的最短路程。
题解&＃xff1a;
与传统TSP相比&＃xff0c;唯一变化的条件是每个节点可以经过多次。
所以也就是转移的时候不用再判断要去的节点j是否去过。
先floyd预处理出两点之间最短路。然后把(!((state>>j)&1))去掉&＃xff0c;套TSP模板就好啦。
AC Code:
1 #include
2 #include
3 #include <string.h>
4 #include
5 #define MAX_N 15
6 #define MAX_S (1<<13)
7 #define INF 10000000
8
9 using namespace std;
10
11 int n;
12 int ans;
13 int dp[MAX_S][MAX_N];
14 int dis[MAX_N][MAX_N];
15
16 void floyd()
17 {
18 for(int k&＃61;0;k<&＃61;n;k&＃43;&＃43;)
19 {
20 for(int i&＃61;0;i<&＃61;n;i&＃43;&＃43;)
21 {
22 for(int j&＃61;0;j<&＃61;n;j&＃43;&＃43;)
23 {
24 if(i!&＃61;j && j!&＃61;k && i!&＃61;k)
25 {
26 dis[i][j]&＃61;min(dis[i][j],dis[i][k]&＃43;dis[k][j]);
27 }
28 }
29 }
30 }
31 }
32
33 void read()
34 {
35 for(int i&＃61;0;i<&＃61;n;i&＃43;&＃43;)
36 {
37 for(int j&＃61;0;j<&＃61;n;j&＃43;&＃43;)
38 {
39 cin>>dis[i][j];
40 }
41 }
42 }
43
44 void solve()
45 {
46 floyd();
47 memset(dp,-1,sizeof(dp));
48 dp[0][0]&＃61;0;
49 for(int state&＃61;0;state<(1<<(n&＃43;1));state&＃43;&＃43;)
50 {
51 for(int i&＃61;0;i<&＃61;n;i&＃43;&＃43;)
52 {
53 if(dp[state][i]!&＃61;-1)
54 {
55 for(int j&＃61;0;j<&＃61;n;j&＃43;&＃43;)
56 {
57 if(dp[state|(1<
58 {
59 dp[state|(1<
60 }
61 }
62 }
63 }
64 }
65 ans&＃61;INF;
66 for(int i&＃61;0;i<&＃61;n;i&＃43;&＃43;)
67 {
68 if(dp[(1<<(n&＃43;1))-1][i]!&＃61;-1)
69 {
70 ans&＃61;min(ans,dp[(1<<(n&＃43;1))-1][i]&＃43;dis[i][0]);
71 }
72 }
73 }
74
75 void print()
76 {
77 cout<
78 }
79
80 int main()
81 {
82 while(cin>>n)
83 {
84 if(n&＃61;&＃61;0) break;
85 read();
86 solve();
87 print();
88 }
89 }
京公网安备 11010802041100号