【牛客】-E 小红勇闯地下城

一语点醒雾中人：看出最短路问题（dijkstra）

ACocde:

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
#define int long long

int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, 1, 0, -1};
struct E {
	int w;
	int x, y;
	bool operator<(const E &u) const {
		return w > u.w;
	}
};
int n, m, h;
int u, v, uu, vv;

void solve() {

	cin >> n >> m >> h;
	char mp[n + 10][m + 10];
	int dis[n + 10][m + 10];
	bool vis[n + 10][m + 10];
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, false, sizeof(vis));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> mp[i][j];
			if (mp[i][j] == 'T')uu = i, vv = j;
			if (mp[i][j] == 'S')u = i, v = j;
		}

	priority_queue<E> q;
	q.push({0, u, v});
	dis[u][v] = 0;

	while (!q.empty()) {
		E t = q.top();
		int x = t.x, y = t.y;
		int w = t.w;
		q.pop();
		if (vis[x][y])
			continue;
		vis[x][y] = 1;
		for (int g = 1; g <= 4; g++) {
			int i = x + dx[g], j = y + dy[g];
			if (i > n || i < 1 || j > m || j < 1)	continue;
			if (i == uu && j == vv) {
				dis[uu][vv] = min(dis[uu][vv], dis[x][y]);
			}
			int ww = w + mp[i][j] - '0';
			if (ww < dis[i][j]) {
				dis[i][j] = ww;
				q.push({ww, i, j});
			}
		}
	}
	if (dis[uu][vv] < h)
		cout << "Yes\n";
	else
		cout << "No\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--)	{
		solve();
	}
	return 0;
}