HDu 4568(SPFA前処理+TSP)
16954 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4568
構想:まずspfaで宝と宝の間の最短距離を前処理して、宝から境界までの最短距離、それから経典のTSPを求める過程です.
View Code
構想:まず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