D题求助
求助
为什么我用一个容器记录大于x的商店的坐标。经过两个bfs后,再遍历这个容器找路径最小值会只通过 90.48。。。。
而用题解办法两个for循环找到大于x的商店却是可以通过的。 (我在想这两个方法找大于x的商店的坐标方法不是等价的么)
int main() { int sx, sy, ex, ey; vector<pair<int ,int>> vt; //记录大于x的坐标的容器 cin >> n >> m >> x; cin >> sx >> sy >> ex >> ey; for (int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ cin >> g[i][j]; if(g[i][j] > x) vt.push_back({i,j}); // 记录大于x的坐标 } /*两个bfs求最短路径****/ memset(d1, 0x3f3f3f, sizeof(d1)); memset(d2, 0x3f3f3f, sizeof(d2)); memset(st, false, sizeof(st)); bfs(d1, sx, sy); memset(st, false, sizeof(st)); bfs(d2, ex, ey); /*两个bfs求最短路径****/ ans = 0x3f3f3f; if( vt.size() == 0) { cout << -1; return 0; } // 如果容器为空, 肯定是不存在最短路径? for(int i = 0; i < (int)vt.size(); i++){ int a = vt[i].first; int b = vt[i].second; ans = min(d1[a][b]+d2[a][b], ans); } else cout << ans << endl; //cout << (ans == 0x3f3f3f ? -1:ans); return 0; }