题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2612
题意 有两个人 要去一个城市中的KFC 一个城市中有多个KFC 求两个人到哪一个KFC的总时间最少 求出这个最少的总时间
思路 用BFS打一遍表 求出两个人每人到 每个 KFC 的时间 然后 遍历一下 更新答案
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1); const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 5e4 + 5; const int MOD = 1e9 + 7; int Move[][2] { -1, 0, // up 1, 0, // down 0,-1, // left 0, 1, // right }; struct Node { int x, y, step; }tmp; string G[205]; int v[205][205]; int dis[205][205][2]; int n, m; int sx[2], sy[2]; queue <Node> q; bool ok(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || G[x][y] == '#' || v[x][y] == 1) return false; return true; } void bfs(int vis) { while (!q.empty()) { int x = q.front().x; int y = q.front().y; int step = q.front().step; q.pop(); if (G[x][y] == '@') dis[x][y][vis] = min(dis[x][y][vis], step); for (int i = 0; i < 4; i++) { tmp.x = x + Move[i][0]; tmp.y = y + Move[i][1]; tmp.step = step + 1; if (ok(tmp.x, tmp.y)) { q.push(tmp); v[tmp.x][tmp.y] = 1; } } } } int main() { while (~scanf("%d%d", &n, &m)) { for (int i = 0; i < n; i++) { cin >> G[i]; for (int j = 0; j < m; j++) { if (G[i][j] == 'Y') { sx[0] = i; sy[0] = j; } else if (G[i][j] == 'M') { sx[1] = i; sy[1] = j; } } } memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < 2; i++) { CLR(v); tmp.x = sx[i]; tmp.y = sy[i]; v[tmp.x][tmp.y] = 1; tmp.step = 0; while (!q.empty()) q.pop(); q.push(tmp); bfs(i); } int ans = INF; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (G[i][j] == '@') ans = min(ans, dis[i][j][0] + dis[i][j][1]); } } cout << ans * 11 << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433138.html
相关资源：JAVA上百实例源码以及开源项目