LeeCode 1631 Dijkstra

题意

传送门 LeeCode 1631. 最小体力消耗路径

题解

路径权值为 max{∣hi?hj∣},e(i,j)∈Emax\{|h_i-h_j|\},e(i,j)\in Emax{ ∣hi??hj?∣},e(i,j)∈E，是非严格递增的，那么可以使用 $Dijkstra$ 求解单源最短路。

struct edge
{
    int to, cost;
};
class Solution
{
    
#define maxn 10005typedef pair<int, int> P;public:vector<edge> G[maxn];int dx[4] = {
    0, 0, -1, 1}, dy[4] = {
    1, -1, 0, 0};int dis[maxn];bool used[maxn];void add_edge(int u, int v, int cost){
    G[u].push_back(edge{
    v, cost});G[v].push_back(edge{
    u, cost});}int dijkstra(int s, int t){
    memset(dis, 0x3f, sizeof(dis));dis[s] = 0;priority_queue<P, vector<P>, greater<P>> q;q.push(P(0, s));while (!q.empty()){
    P p = q.top();q.pop();int v = p.second, d = p.first;if (used[v])continue;used[v] = 1;for (int i = 0; i < G[v].size(); ++i){
    edge &e = G[v][i];int d2 = max(d, e.cost);if (d2 < dis[e.to]){
    dis[e.to] = d2;q.push(P(d2, e.to));}}}return dis[t];}int minimumEffortPath(vector<vector<int>> &heights){
    int h = heights.size(), w = heights[0].size();for (int i = 0; i < h; ++i){
    for (int j = 0; j < w; ++j){
    for (int k = 0; k < 4; ++k){
    int nx = i + dx[k], ny = j + dy[k];if (nx >= 0 && nx < h && ny >= 0 && ny < w){
    add_edge(i * w + j, nx * w + ny, abs(heights[i][j] - heights[nx][ny]));}}}}return dijkstra(0, (h - 1) * w + w - 1);}
};