题意：给定一个网格图，图中有一些点要求全部走到，问最少的花费是多少，从任意边界进入，任意边界出去，如果不能够全部走到，输出0。
解法：一次spfa从边界上的所有点出发，计算到K个宝藏的最短路，然后计算出任意两个宝藏之间的最短路，最后状态压缩枚举即可。
代码如下：
#include#include #include #include #include using namespace std;// 记得要带走全部的物品 const int INF = 0x3f3f3f3f;int N, M, K;int mp[205][205];int idis[15][15]; // 这个15*15的矩阵用来保留宝藏之间的最短路程int odis[15]; // 从边界到K个位置的最短距离struct Node { int x, y;}p[15];int que[1000005];int dis[40005];char vis[40005];int dir[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0};bool legal(int x, int y) { if (x < 0 || x >= N || y < 0 || y >= M) return false; return true;}void spfa(int sta, int num) { int front = 0, tail = 0; memset(dis, 0x3f, sizeof (dis)); memset(vis, 0, sizeof (vis)); que[tail++] = sta; dis[sta] = 0, vis[sta] = 1; while (front < tail) { int cur = que[front++], nxt; vis[cur] = 0; int x = cur / M, y = cur % M; int xx, yy; for (int k = 0; k < 4; ++k) { xx = x + dir[k][0], yy = y + dir[k][1]; nxt = xx * M + yy; if (legal(xx, yy)) { if (dis[nxt] > dis[cur] + mp[xx][yy]) { dis[nxt] = dis[cur] + mp[xx][yy]; if (!vis[nxt]) { vis[nxt] = 1; que[tail++] = nxt; } } } } } for (int i = 0; i < K; ++i) { idis[num][i] = dis[p[i].x * M + p[i].y]; }}void bspfa() { int front = 0, tail = 0; memset(dis, 0x3f, sizeof (dis)); memset(vis, 0, sizeof (vis)); for (int i = 0; i < N; ++i) { int k1 = i * M, k2 = i * M + M-1; que[tail++] = k1, que[tail++] = k2; dis[k1] = mp[i][0], dis[k2] = mp[i][M-1]; // 边界点均被初始距离为0加入进来 vis[k1] = vis[k2] = 1; } for (int j = 1; j < M - 1; ++j) { int k1 = j, k2 = (N-1) * M + j; que[tail++] = k1, que[tail++] = k2; dis[k1] = mp[0][j], dis[k2] = mp[N-1][j]; vis[k1] = vis[k2] = 1; } while (front < tail) { int cur = que[front++], nxt; vis[cur] = 0; int x = cur / M, y = cur % M; int xx, yy; for (int k = 0; k < 4; ++k) { xx = x + dir[k][0], yy = y + dir[k][1]; nxt = xx * M + yy; if (legal(xx, yy)) { if (dis[nxt] > dis[cur] + mp[xx][yy]) { dis[nxt] = dis[cur] + mp[xx][yy]; if (!vis[nxt]) { vis[nxt] = 1; que[tail++] = nxt; } } } } } for (int i = 0; i < K; ++i) { odis[i] = dis[p[i].x*M + p[i].y]; }}int f[13][1<<13];// f[i][j]表示状态为j，并且最后走的位置为i的最少开销 int dfs(int sta, int nxt) { if (~f[nxt][sta] && nxt != -1) { return f[nxt][sta]; } if (sta == 0) { return f[nxt][sta] = odis[nxt]; // 从nxt开始进入 } int ret = INF; for (int i = 0; i < K; ++i) { if (sta&(1 << i)) { if (nxt != -1) ret = min(ret, dfs(sta^(1 << i), i) + idis[i][nxt]); else ret = min(ret, dfs(sta^(1 << i), i) + odis[i] - mp[p[i].x][p[i].y]); // 走i点走出去的 } } return f[nxt][sta] = ret;} int solve() { memset(f, 0x3f, sizeof (f)); int mask = 1 << K; for (int i = 0; i < K; ++i) f[i][1<