合理建模--最短路径

这道题目难就难在如何想到用最短路径来做 主要是这个题目不能用bfs来写，因为距离并不是1 狄克斯特拉算法很久没写了，有些地方生疏了 且这个题目需要记录三个信息，得用tuple

---

题目地址

int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; class Solution { public: int minTimeToReach(vector<vector<int>>& moveTime) { int n = moveTime.size(); int m = moveTime[0].size(); vector<vector<int>> dis (n,vector<int> (m,0x3f3f3f3f)); priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> q; q.emplace(0,0,0); while(q.size()){ auto [d,i,j] = q.top(); q.pop(); if(i==n-1 && j == m-1){ return d; } if(dis[i][j]!=0x3f3f3f3f) continue; for(int k=0;k<4;k++){ int x = i+dx[k], y = j + dy[k]; if(x<0 || x >= n || y <0 || y>=m) continue; int now = max(d,moveTime[x][y]) + 1; if(now<dis[x][y]){ dis[x][y] = now; q.emplace(now,x,y); } } } return -1; } };