HDOJ搜索专题之下沙小面的(2)

题目的模型：在一个图中，给定一系列目标结点，求从起点出发经过所有目标结点的最短距离。

分析：由于目标结点数目最大为7，所以可以暴力搜索过，枚举经过目标结点的排列，然后计算选择最优的。计算距离时需要用floyd预处理任意2结点之间的最短距离。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 31
 4 #define MIN(a,b) ((a)<(b)?(a):(b))
 5 #define INF 0x7fffffff
 6 int d[N][N],t[N],a[N],n,m,cnt,ans;
 7 char vis[N];
 8 void dfs()
 9 {
10   if(cnt==m)
11   {
12     int dist=d[0][t[a[0]]];
13     for(int i=1;i<m;i++)  dist+=d[t[a[i-1]]][t[a[i]]];
14     ans=MIN(ans,dist);
15     return;
16   }
17   for(int i=0;i<m;i++)
18   {
19     if(vis[i])  continue;
20     vis[i]=1;
21     a[cnt++]=i;
22     dfs();
23     cnt--;
24     vis[i]=0;
25   }
26 }
27 int main()
28 {
29   while(scanf("%d",&n))
30   {
31     if(n==0)  break;
32     for(int i=0;i<n;i++)
33     {
34       for(int j=0;j<n;j++)  scanf("%d",&d[i][j]);
35     }
36     scanf("%d",&m);
37     for(int i=0;i<m;i++)  scanf("%d",&t[i]);
38     for(int k=0;k<n;k++)
39     {
40       for(int i=0;i<n;i++)
41       {
42         for(int j=0;j<n;j++)  d[i][j]=MIN(d[i][j],d[i][k]+d[k][j]);
43       }
44     }
45     ans=INF;
46     cnt=0;
47     memset(vis,0,sizeof(vis));
48     dfs();
49     printf("%d\n",ans);
50   }
51   return 0;
52 }