这道题是长沙邀请赛的题，当时是道签到题。
这种题还是很常见的，讲一下思路。
首先是预处理出每个宝藏之间的距离，还有到边的距离，直接对每个宝藏进行一次SPFA就可以了。
然后就是经典的求TSP的过程。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 1111111111
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define infA(a) for (int i = 0 ; i <= n ; ++ i)a[i] = inf ;
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a) {
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
#define N 222
#define K 15
int Map[N][N] ;
struct tru {
int x ,y ;
} tk[K] ;
int tt ;
int MM[K][K] ;
int dp[1 << K][K] ;
int dis[N][N] ;
bool vis[N][N] ;
PII qe[1111111] ;
int D[K] ;
int n , m ;
int mx[4] = {0 , 0 , 1 , -1} ;
int my[4] = {1 , -1 , 0 , 0} ;
int inmap(int x ,int y) {
if(x >= 0 && x < n && y >= 0 && y < m && Map[x][y] != -1)return 1 ;
return 0 ;
}
void init(int pos) {
for (int i = 0 ; i < n ; i ++ ) {
for (int j = 0 ; j < m ; j ++ ) {
dis[i][j] = inf ;
vis[i][j] = 0 ;
}
}
dis[tk[pos].x][tk[pos].y] = Map[tk[pos].x][tk[pos].y] == -1 ? inf : 0 ;
int h = 0 , t = 0 ;
qe[h ++ ] = mp(tk[pos].x ,tk[pos].y) ;
while(h > t) {
PII tp = qe[t ++ ] ;
vis[tp.FI][tp.SE] = 0 ;
if(tp.FI == 0 || tp.FI == n - 1 || tp.SE == 0 || tp.SE == m - 1) {
D[pos] = min(D[pos] , dis[tp.FI][tp.SE]) ;
}
for (int i = 0 ; i < 4 ; i ++ ) {
int tx = tp.FI + mx[i] ;
int ty = tp.SE + my[i] ;
if(inmap(tx , ty)) {
if(dis[tx][ty] > dis[tp.FI][tp.SE] + Map[tx][ty]) {
dis[tx][ty] = dis[tp.FI][tp.SE] + Map[tx][ty] ;
if(!vis[tx][ty]) {
vis[tx][ty] = 1 ;
qe[h ++ ] = mp(tx ,ty) ;
}
}
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin) ;
freopen("out.txt","w",stdout) ;
#endif
int T ;
cin >> T ;
while ( T -- ) {
cin >> n >> m ;
REP(i , 0, n - 1 ) {
REP(j , 0 , m - 1)scanf("%d",&Map[i][j]) ;
}
cin >> tt ;
REP(i , 0 , tt - 1) {
RD(tk[i].x) ;
RD(tk[i].y) ;
}
REP(i , 0 , tt - 1) {
REP(j , 0 , tt - 1) {
MM[i][j] = inf ;
}
MM[i][i] = 0 ;
D[i] = inf ;
}
for (int i = 0 ; i < (1 << tt) ; i ++ ) {
for (int j = 0 ; j < tt ; j ++ )dp[i][j] = inf ;
}
REP(i , 0 , tt - 1) {
init(i) ;
REP(j , 0 , tt - 1) {
if(i == j)continue ;
MM[i][j] = min(MM[i][j] , dis[tk[j].x][tk[j].y]) ;//宝藏到宝藏之间的最近距离
}
dp[1 << i][i] = D[i] + Map[tk[i].x][tk[i].y] ;//该宝藏到达边的最近距离
}
for (int i = 0 ; i < 1 << tt ; i ++ ) {
for (int j = 0 ; j < tt ; j ++ ) {
if(i & (1 << j) == 0)continue ;
if(dp[i][j] == inf)continue ;
for (int k = 0 ; k < tt ; k ++ ) {
if(i & (1 << k))continue ;
int tp = i | (1 << k) ;
dp[tp][k] = min(dp[tp][k] , dp[i][j] + MM[j][k]) ;
}
}
}
int ans = inf ;
for (int i = 0 ; i < tt ; i ++ ) {
ans = min(ans , dp[(1 << tt) - 1][i] + D[i] ) ;
}
cout << ans << endl;
}
return 0 ;
}
/*
5
4 4
3 3 3 3
3 -1 -1 -1
3 -1 3 3
3 -1 -1 -1
1
2 2
5 5
1 1 1 1 1
1 -1 -1 -1 -1
1 -1 -1 -1 -1
1 -1 -1 -1 -1
1 -1 -1 -1 -1
2
4 0
0 4
3 3
3 2 3
5 4 3
1 4 2
1
1 1
3 3
3 2 3
5 4 3
1 4 2
2
1 1
2 2
*/