POJ3311HiewiththePie：TSP（旅行商）【节点可多次经过】

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<1 || dp[state|(1<dp[state][i]&＃43;dis[i][j])
58 {
59 dp[state|(1<dis[i][j];
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<endl;
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 }