http://acm.hdu.edu.cn/showproblem.php?pid=4568
题意：
网格图中有若干个宝藏，探索每个方格都有相应的代价
每个途径的格子都要进行探索
告诉你宝藏的位置
问从方格外开始探索到所有宝藏并回到出发点的最小代价
spfa求出从方格外到每个宝藏的最小代价，以及每两个宝藏之间的最小代价
然后就是经典的旅行商问题
详情参见https://www.cnblogs.com/TheRoadToTheGold/p/12384542.html
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 201
#define M 14
int n,m,tot;
int a[N][N];
int tx[M],ty[M];
int dis[M][M];
struct node
{
int x,y,d;
}now,nxt;
queue<node>q;
int f[N][N];
bool vis[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int dp[1<<M][M];
void bfs(int s)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
f[i][j]=1e9;
now.d=0;
if(!s)
{
now.x=1;
for(int i=1;i<=m;++i)
if(!vis[1][i] && a[1][i]!=-1)
{
now.y=i;
q.push(now);
vis[1][i]=true;
f[1][i]=a[1][i];
}
now.x=n;
for(int i=1;i<=m;++i)
if(!vis[n][i] && a[n][i]!=-1)
{
now.y=i;
q.push(now);
vis[n][i]=true;
f[n][i]=a[n][i];
}
now.y=1;
for(int i=1;i<=n;++i)
if(!vis[i][1] && a[i][1]!=-1)
{
now.x=i;
q.push(now);
vis[i][1]=true;
f[i][1]=a[i][1];
}
now.y=m;
for(int i=1;i<=n;++i)
if(!vis[i][m] && a[i][m]!=-1)
{
now.x=i;
q.push(now);
vis[i][m]=true;
f[i][m]=a[i][m];
}
}
else
{
now.x=tx[s];
now.y=ty[s];
q.push(now);
vis[now.x][now.y]=true;
f[now.x][now.y]=0;
}
while(!q.empty())
{
now=q.front();
q.pop();
vis[now.x][now.y]=false;
for(int i=0;i<4;++i)
{
nxt.x=now.x+dx[i];
nxt.y=now.y+dy[i];
if(nxt.x && nxt.x<=n && nxt.y && nxt.y<=m && a[nxt.x][nxt.y]!=-1 && f[nxt.x][nxt.y]>f[now.x][now.y]+a[nxt.x][nxt.y])
{
f[nxt.x][nxt.y]=f[now.x][now.y]+a[nxt.x][nxt.y];
if(!vis[nxt.x][nxt.y])
{
q.push(nxt);
vis[nxt.x][nxt.y]=true;
}
}
}
}
for(int i=1;i<=tot;++i) dis[s][i]=f[tx[i]][ty[i]];
}
int main()
{
int T,S;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
scanf("%d",&tot);
for(int i=1;i<=tot;++i)
{
scanf("%d%d",&tx[i],&ty[i]);
tx[i]++;
ty[i]++;
}
bfs(0);
for(int i=1;i<=tot;++i) bfs(i);
S=(1<<tot+1)-1;
for(int i=1;i<=S;++i)
for(int j=0;j<=tot;++j)
dp[i][j]=1e9;
for(int i=1;i<=tot;++i) dp[0][i]=dis[0][i]-a[tx[i]][ty[i]];
for(int i=1;i<S;++i)
for(int j=0;j<=tot;++j)
if(!(i&1<<j))
for(int k=1;k<=tot;++k)
if(i&1<<k)
dp[i][j]=min(dp[i][j],dis[j][k]+dp[i^1<<k][k]);
printf("%d\n",dp[S-1][0]);
}
}
Hunter
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2804 Accepted Submission(s): 899
The area can be represented as a N*M rectangle. Any points of the rectangle is a number means the cost of research it,-1 means James can't cross it, James can start at any place out of the rectangle, and explore point next by next. He will move in the rectangle and bring out all treasures he can take. Of course, he will end at any border to go out of rectangle(James will research every point at anytime he cross because he can't remember whether the point are researched or not).
Now give you a map of the area, you must calculate the least cost that James bring out all treasures he can take(one point up to only one treasure).Also, if nothing James can get, please output 0.