hdu 4568 Hunter(spfa预处理 + 状压dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4568

思路：首先spfa预处理出每对宝藏之间的最短距离以及宝藏到边界的最短距离，然后dp[state][u]表示当前在点u，状态为state的最短距离，然后更新就行。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int MAX_N = (233);

const int inf = 0x3f3f3f3f;

int N, M, n, g[MAX_N][MAX_N];

struct Point {

	int x, y;

} point[14];

int d[14][14], dd[14], dp[(1 << 14) + 4][14]; //d[i][j]表示宝藏i到宝藏j之间的最短距离，dd[i]表示宝藏i到边界的最短距离

bool vis[MAX_N][MAX_N];

struct Node {

	int x, y, step;

	Node () {}

	Node (int _x, int _y, int _step) : x(_x), y(_y), step(_step) {}

};

int dist[MAX_N][MAX_N], dir[4][2] = {

	{-1, 0}, {1, 0}, {0, -1}, {0, 1}

};

void spfa(int index)

{

	for (int i = 0; i < N; ++i) {

		for (int j = 0; j < M; ++j) dist[i][j] = inf, vis[i][j] = false;

	}

	queue<pair<int, int > > que;

	que.push(make_pair(point[index].x, point[index].y));

	dist[point[index].x][point[index].y] = 0;

	while (!que.empty()) {

		pair<int, int > p = que.front();

		que.pop();

		vis[p.first][p.second] = false;

		for (int i = 0; i < 4; ++i) {

			int x = p.first + dir[i][0];

			int y = p.second + dir[i][1];

			if (g[x][y] == -1) continue;

			if (x < 0 || x >= N || y < 0 || y >= M) {

				dd[index] = min(dd[index], dist[p.first][p.second] + g[point[index].x][point[index].y]);

				continue;

			}

			if (dist[p.first][p.second] + g[x][y] < dist[x][y]) {

				dist[x][y] = dist[p.first][p.second] + g[x][y];

				if (!vis[x][y]) {

					vis[x][y] = true;

					que.push(make_pair(x, y));

				}

			}

		}

	}

}

int main()

{

	int Cas;

	scanf("%d", &Cas);

	while (Cas--) {

		scanf("%d %d", &N, &M);

		for (int i = 0; i < N; ++i) {

			for (int j = 0; j < M; ++j) scanf("%d", &g[i][j]);

		}

		scanf("%d", &n);

		for (int i = 0; i < n; ++i) scanf("%d %d", &point[i].x, &point[i].y);

		for (int i = 0; i < (1 << n); ++i) {

			for (int j = 0; j < n; ++j) dp[i][j] = inf;

		}

		memset(dd, 0x3f, sizeof(dd));

		for (int i = 0; i < n; ++i) {

			spfa(i);

			for (int j = 0; j < n; ++j) {

				if (i == j) d[i][j] = 0;

				else d[i][j] = dist[point[j].x][point[j].y];

			}

			dp[1 << i][i] = dd[i];

		}

		for (int s = 0; s < (1 << n); ++s) {

			for (int i = 0; i < n; ++i) {

				if ( dp[s][i] != inf && ((1 << i) & s)) {

					for (int j = 0; j < n; ++j) if (i != j && (!((1 << j) &s))) {

						dp[s | (1 << j)][j] = min(dp[s | (1 << j)][j], dp[s][i] + d[i][j]);

					}

				}

			}

		}

		int ans = inf;

		for (int i = 0; i < n; ++i) {

			ans = min(ans, dp[(1 << n) - 1][i] + dd[i] - g[point[i].x][point[i].y]);

		}

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

hdu 4568 Hunter(spfa预处理 + 状压dp)

最新文章

热门文章