【問題描述】
n個(gè)人在做傳遞物品的游戲,編號(hào)為1-n。
游戲規(guī)則是這樣的：開始時(shí)物品可以在任意一人手上，他可把物品傳遞給其他人中的任意一位；下一個(gè)人可以傳遞給未接過物品的任意一人。
即物品只能經(jīng)過同一個(gè)人一次，而且每次傳遞過程都有一個(gè)代價(jià)；不同的人傳給不同的人的代價(jià)值之間沒有聯(lián)系；
求當(dāng)物品經(jīng)過所有n個(gè)人后，整個(gè)過程的總代價(jià)是多少。
【輸入】
第一行為n,表示共有n個(gè)人（16>=n>=2）；
以下為n*n的矩陣，第i+1行、第j列表示物品從編號(hào)為i的人傳遞到編號(hào)為j的人所花費(fèi)的代價(jià)，特別的有第i+1行、第i列為-1（因?yàn)槲锲凡荒茏约簜鹘o自己），其他數(shù)據(jù)均為正整數(shù)(<=10000)。
(對(duì)于50%的數(shù)據(jù)，n<=11)。
【輸出】
一個(gè)數(shù)，為最小的代價(jià)總和。
【樣例輸入】
2
-1 9794
2724 –1
【樣例輸出】
2724
時(shí)間到了啊~ 明天再繼續(xù)寫。
是一個(gè)用二進(jìn)制來表示圖的狀態(tài)的動(dòng)態(tài)規(guī)劃，或者說是記憶化搜索。f[i][j]中，i來表示圖的二進(jìn)制狀態(tài)，j表示這個(gè)狀態(tài)中第一個(gè)點(diǎn)。
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 20
4: #define MAXINT 1000000
5: using namespace std;
6:
7: int dis[maxn][maxn];
8: int n;
9: int f[70000][20];
10: int ans=MAXINT;
11:
12: int find(int a,int b)
13: {
14: if (f[a][b]!=MAXINT) return f[a][b];
15: int tem=a;
16: a-=(1<<b);
17: if (!a)
18: {
19: f[tem][b]=0;
20: return 0;
21: }
22: for (int i=0;i<n;++i)
23: if ((1<<i)&a)
24: f[tem][b]=min(find(a,i)+dis[b][i],f[tem][b]);
25: return f[tem][b];
26: }
27:
28: int main()
29: {
30: freopen("input.txt","r",stdin);
31: freopen("output.txt","w",stdout);
32:
33: scanf("%d",&n);
34: for (int i=0;i<n;++i)
35: for (int j=0;j<n;++j)
36: scanf("%d",&dis[i][j]);
37: for (int i=0;i<(1<<n);++i)
38: for (int j=0;j<n;++j)
39: f[i][j]=MAXINT;
40: for (int i=0;i<n;++i)
41: if (find((1<<n)-1,i)<ans)
42: ans=find((1<<n)-1,i);
43: printf("%d\n",ans);
44: return 0;
45: }
46: