本文共 1598 字，大约阅读时间需要 5 分钟。

分析

在路径搜索问题中，优先队列能够有效地提高搜索效率。本文采用手写队列的方式，每次进行BFS后对队列进行排序，之后每次取出的队头元素的权值一定是最小的。这种方法能够确保在有限的时间内找到权值最小的路径。

C++代码

class Solution {public:    int n, m, hh = 0, tt = -1, ans = -1;    int dx[4] = {0, 1, 0, -1};    int dy[4] = {1, 0, -1, 0};    struct node {        int x, y, w;        bool operator<(const node& p) {            return w < p.w;        }    };    q[55*55];    int bfs(vector
   
    
     >& grid) {        bool st[n+1][m+1];        memset(st, 0, sizeof st);        node t;        t.x = 0, t.y = 0, t.w = grid[0][0];        q[++tt] = t;        st[0][0] = true;        while (hh <= tt) {            t = q[hh++];            ans = max(ans, t.w);            node cur;            for (int i = 0; i < 4; i++) {                cur.x = t.x + dx[i];                cur.y = t.y + dy[i];                if (cur.x == n-1 && cur.y == m-1) {                    cur.w = grid[cur.x][cur.y];                    q[++tt] = cur;                    ans = max(ans, cur.w);                    return 0;                }                if (cur.x >= 0 && cur.x < n && cur.y >= 0 && cur.y < m && !st[cur.x][cur.y]) {                    cur.w = grid[cur.x][cur.y];                    st[cur.x][cur.y] = true;                    q[++tt] = cur;                }            }            sort(q + hh, q + tt + 1);        }        return 0;    }    int swiminwater(vector
     
      
       >& grid) {        if (grid.size() < 1) return 0;        n = grid.size();        m = grid[0].size();        bfs(grid);        return ans;    }}
      
     
    
   

上述代码实现了基于优先队列的最短路径算法。通过手写队列的方式，每次BFS后对队列进行排序，确保每次取出的队头元素权值最小，从而保证路径搜索的高效性。