hdu 4568(SPFA预处理+TSP)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4568
思路：先用spfa预处理出宝藏与宝藏之间的最短距离，宝藏到边界的最短距离，然后就是经典的求TSP过程了。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 #define MAXN 222
  8 #define inf 1<<30
  9 
 10 struct Point{
 11     int x,y;
 12 }point[MAXN];
 13 
 14 int value[MAXN][MAXN];//原图
 15 int map[MAXN][MAXN];//宝藏间的最短距离
 16 int dist[MAXN][MAXN];//宝藏到边界的距离
 17 int dd[MAXN];//宝藏到达边界的最短距离
 18 bool mark[MAXN][MAXN];
 19 int dp[1<<14][14];
 20 int n,m,k;
 21 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
 22 
 23 void spfa(int num)
 24 {
 25     memset(mark,false,sizeof(mark));
 26     for(int i=0;i<n;i++)
 27         for(int j=0;j<m;j++)dist[i][j]=inf;
 28     queue<pair<int,int> >que;
 29     que.push(make_pair(point[num].x,point[num].y));
 30     if(dist[point[num].x][point[num].y]==-1)return;
 31     dist[point[num].x][point[num].y]=0;
 32     while(!que.empty()){
 33         int x=que.front().first,y=que.front().second;
 34         que.pop();
 35         mark[x][y]=false;
 36         if(x==0||x==(n-1)||y==0||y==(m-1)){
 37             dd[num]=min(dd[num],dist[x][y]);
 38         }
 39         for(int i=0;i<4;i++){
 40             int xx=x+dir[i][0],yy=y+dir[i][1];
 41             if(xx>=0&&xx<n&&yy>=0&&yy<m&&value[xx][yy]!=-1){
 42                 if(dist[x][y]+value[xx][yy]<dist[xx][yy]){
 43                     dist[xx][yy]=dist[x][y]+value[xx][yy];
 44                     if(!mark[xx][yy]){
 45                         mark[xx][yy]=true;
 46                         que.push(make_pair(xx,yy));
 47                     }
 48                 }
 49             }
 50         }
 51     }
 52 }
 53 
 54 
 55 int main()
 56 {
 57     int _case;
 58     scanf("%d",&_case);
 59     while(_case--){
 60         scanf("%d%d",&n,&m);
 61         for(int i=0;i<n;i++)
 62             for(int j=0;j<m;j++)
 63                 scanf("%d",&value[i][j]);
 64         scanf("%d",&k);
 65         for(int i=0;i<k;i++)scanf("%d%d",&point[i].x,&point[i].y);
 66         for(int i=0;i<k;i++)
 67             for(int j=0;j<k;j++)
 68                 map[i][j]=(i==j)?0:inf;
 69         for(int i=0;i<(1<<k);i++)
 70             for(int j=0;j<k;j++)dp[i][j]=inf;
 71         fill(dd,dd+MAXN,inf);
 72         for(int i=0;i<k;i++){
 73             spfa(i);
 74             for(int j=0;j<k;j++){
 75                 if(i==j)continue;
 76                 map[i][j]=min(map[i][j],dist[point[j].x][point[j].y]);//宝藏与宝藏之间的最近距离
 77             }
 78             dp[1<<i][i]=dd[i]+value[point[i].x][point[i].y];//宝藏到边的最近距离
 79         }
 80         for(int s=0;s<(1<<k);s++){
 81             for(int i=0;i<k;i++){
 82                 if(s&(1<<i)==0)continue;
 83                 if(dp[s][i]==inf)continue;
 84                 for(int j=0;j<k;j++){
 85                     if(s&(1<<j)==1)continue;
 86                     dp[s|(1<<j)][j]=min(dp[s|(1<<j)][j],dp[s][i]+map[i][j]);
 87                 }
 88             }
 89         }
 90         int ans=inf;
 91         for(int i=0;i<k;i++){
 92             ans=min(ans,dp[(1<<k)-1][i]+dd[i]);//拿到了所有的宝藏之后还要走出来
 93         }
 94         printf("%d
",ans);
 95     }
 96     return 0;
 97 }
 98 
 99 
100             
101 
102 
103
View Code