一个饥饿的人被困在了迷宫当中，渴望走出迷宫。 迷宫的大小为 n × m n×m 但很可惜，有很多位置是不能走的。 每一步，你都可以向上下左右移动一次，花费一秒的时间。 但是迷宫被一种魔法包裹，只有移动时间恰好为 s s 秒的人才能走出去。 而你在迷宫中捡到了一个机器，可以帮助你在每一次向上下移动时消耗 k k 秒的时间，而左右走并不会消耗 k k 秒。 那么你能找到一个最小的正实数 k k 使得从起点到终点的最短用时等于 s s 吗？ 数据保证有解（用c++）

这个问题可以建模为一个带有参数的最短路径问题，我们需要找到最小的正实数k，使得从起点到终点的最短路径时间恰好等于s。我们可以使用二分搜索来寻找合适的k值，因为随着k的增加，最短路径时间是单调不减的。 以下是C++的实现： ```cpp #include <iostream> #include <vector> #include <queue> #include <tuple> #include <cmath> #include <climits> using namespace std; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; bool is_valid(int x, int y, int n, int m, const vector<vector<bool>>& grid) { return x >= 0 && x < n && y >= 0 && y < m && grid[x][y]; } double find_min_k(int n, int m, const vector<vector<bool>>& grid, pair<int, int> start, pair<int, int> end, double s) { double low = 1e-9; double high = 1e9; double ans = high; for (int iter = 0; iter < 100; ++iter) { double mid = (low + high) / 2; vector<vector<double>> dist(n, vector<double>(m, 1e18)); priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq; dist[start.first][start.second] = 0; pq.emplace(0, start.first, start.second); while (!pq.empty()) { auto [d, x, y] = pq.top(); pq.pop(); if (d > dist[x][y]) continue; if (x == end.first && y == end.second) break; for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (!is_valid(nx, ny, n, m, grid)) continue; double cost = (dir < 2) ? mid : 1.0; // 上下方向消耗mid秒，左右消耗1秒 if (dist[nx][ny] > dist[x][y] + cost) { dist[nx][ny] = dist[x][y] + cost; pq.emplace(dist[nx][ny], nx, ny); } } } if (dist[end.first][end.second] <= s) { ans = mid; high = mid; } else { low = mid; } } return ans; } int main() { int n, m; cin >> n >> m; vector<vector<bool>> grid(n, vector<bool>(m)); pair<int, int> start, end; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c; cin >> c; grid[i][j] = (c != '#'); if (c == 'S') start = {i, j}; if (c == 'E') end = {i, j}; } } double s; cin >> s; double k = find_min_k(n, m, grid, start, end, s); cout.precision(10); cout << fixed << k << endl; return 0; } ``` 1. 二分搜索的精度需要足够高，这里进行了100次迭代以确保精度。 2. 使用优先队列实现的Dijkstra算法来计算最短路径，因为图中可能存在负权边（当k很小时）。 3. 需要确保在计算最短路径时正确处理上下方向和左右方向的不同时间消耗。 [2025-07-06 15:50:00 | AI写代码神器 | 838点数解答]