关于一道 AtCoder Beginner Contest 的题的一个疑问
我在补一道 ABC 的题 的时候交了一发代码，思路是先求出由药，起点和终点构成的小图，再在小图上判断可不可以达到终点。由于判断时用了最朴素的搜索，超时了，于是加上了一个优化，维护到达每一个点的最大能量，如果当前方案不是最优方案，则舍弃。但是在实现时将维护最大变成了维护最小值，但是通过了，改回来后样例都不是对的，求解释。
题目：
有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i, j)$ 表示从上往下第 $i$ 行，从左往上第 $j$ 列的单元格。每个单元格的状态由字符 $A_{i,j}$ 表示，其含义如下：
.:空单元格。#:一个障碍物。S:空单元格和起点。T:空单元格和目标点。
高桥可以通过消耗 $1$ 能量从当前单元格移动到垂直或水平相邻的空单元格。如果能量为 $0$ ，则无法移动，也无法离开网格。
网格中有 $N$ 种药物。 $i$ -th药品位于空格 $(R_i, C_i)$ 处，可以用来将能量为 $E_i$ 。注意，能量并不一定会增加。他可以在当前格子中使用药物。使用过的药品会消失。
高桥以 $0$ 的能量从起点开始，并希望到达目标点。请判断这是否可行。
Code：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
#include <time.h>
using namespace std;
int h, w, a[300][300];
char m[300][300];
int n;
int dis[400][400]; //小图上两个点之间的距离
int x[400], y[400]; //小图上每一个点对应原来坐标系上的位置，起点1，终点2
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
void bfs(int idx) { //求出距离
int dist[300][300];
memset(dist, 0x3f, sizeof(dist));
dist[x[idx]][y[idx]] = 0;
queue<int> q;
q.push(x[idx]);
q.push(y[idx]);
while (q.size()) {
int nowx = q.front();
q.pop();
int nowy = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = nowx + dx[i], ny = nowy + dy[i];
if (nx >= 1 && nx <= h && ny >= 1 && ny <= w && dist[nx][ny] == 0x3f3f3f3f && m[nx][ny] != '#') {
dist[nx][ny] = dist[nowx][nowy] + 1;
q.push(nx);
q.push(ny);
}
}
}
for (int i = 1; i <= n + 2; i++) {
dis[idx][i] = dist[x[i]][y[i]];
}
}
bool vis[300][300];
int dis1[400];
void dfs(const int u, int t) { //在小图上操作
if (t < dis1[u]) dis1[u] = t;
else return;
int p = x[u], q = y[u];
vis[x[u]][q] = 1;
if (p == x[2] && q == y[2]) {
cout << "Yes";
exit(0);
}
int tmp = a[p][q];
if (t < a[p][q] && a[p][q]) {
t = a[p][q], a[p][q] = 0;
}
for (int i = 1; i <= n + 2; i++) {
if ((x[i] != p || y[i] != q) && !vis[x[i]][y[i]] && t >= dis[u][i]) {
t -= dis[u][i];
dfs(i, t);
t += dis[u][i];
}
}
a[p][q] = tmp;
vis[p][q] = 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> h >> w;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> m[i][j];
if (m[i][j] == 'S') {
x[1] = i, y[1] = j;
}
if (m[i][j] == 'T') {
x[2] = i, y[2] = j;
}
}
}
cin >> n;
for (int i = 1; i <= n; i++) {
int r, c, e;
cin >> r >> c >> e;
a[r][c] = e;
x[i + 2] = r, y[i + 2] = c;
}
for (int i = 1; i <= n * 2; i++) {
bfs(i);
}
memset(dis1, 0x3f, sizeof(dis1));
dfs(1, 0);
cout << "No";
return 0;
}
