algo-aha

Dijkstra算法，用优先队列的图遍历

• https://leetcode.com/problems/network-delay-time/

注： 比较函数若使用c++中的引用语法[&dist](){...}，优先队列中可不用存节点距离d。这里用各语言通用的写法。

int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    // dijkstra算法
    unordered_map<int, unordered_map<int, int>> adj;
    for (auto &e : times) {
        adj[e[0]][e[1]] = e[2];
    }
    vector<int> dist(N + 1, INT_MAX); // 节点1..N
    dist[K] = 0;

    using arr2 = array<int, 2>; // [dist, node]
    auto cmp = [](arr2 &a, arr2 &b) { 
        return a[0] > b[0]; // 最小堆
    };
    priority_queue<arr2, vector<arr2>, decltype(cmp)> pq(cmp);
    pq.push({dist[K], K});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        for (auto& [v, cost] : adj[u]) { // 遍历u的所有邻接点
            int newdist = d + cost;
            if (newdist < dist[v]) {
                dist[v] = newdist;
                pq.push({newdist, v});
            }
        }
    }

    int ans = INT_MIN;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, dist[i]);
    }
    return (ans != INT_MAX) ? ans : -1;
}

Bellman-Ford算法

对所有边做V-1遍松弛（V个顶点的最短路径最多有V-1条边）。根据上一遍的距离值prev[]更新这一遍的距离值dist[]。

• https://leetcode.com/problems/network-delay-time/>]

int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    // Bellman-Ford算法，对所有边做N-1次松弛
    const int INF = 1e7;
    vector<int> dist(N + 1, INF);
    dist[K] = 0;
    for (int i = 1; i < N; i++) {
        auto prev = dist;
        for (auto &e : times) {
            int u = e[0], v = e[1], cost = e[2];
            dist[v] = min(dist[v], prev[u] + cost);
        }
    }

    int ans = INT_MIN;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, dist[i]);
    }
    return (ans != INF) ? ans : -1;
}

• https://leetcode.com/problems/cheapest-flights-within-k-stops/

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    // 从src到dst最多K个中间站，共V=K+2个节点
    // Bellman-Ford算法，对所有边做V-1=K+1次松弛
    const int INF = 1e7;
    vector<int> dist(n, INF); // src到各节点的距离
    dist[src] = 0;
    for (int i = 0; i <= K; i++) {
        auto prev = dist;
        for (auto &e : flights) {
            int u = e[0], v = e[1], cost = e[2];
            dist[v] = min(dist[v], prev[u] + cost);
        }
    }
    return (dist[dst] != INF) ? dist[dst] : -1;
}

BFS

• https://leetcode.com/problems/shortest-path-in-binary-matrix/

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    // 从左上角到右下角的最短路径，bfs
    if (grid[0][0] == 1) return -1;
    const int R = grid.size(), C = grid[0].size();
    vector<vector<bool>> visited(R, vector<bool>(C, false));
    using arr3 = array<int, 3>; // [dist, i, j]
    queue<arr3> q;
    q.push({1, 0, 0});
    visited[0][0] = true;

    while (!q.empty()) {
        auto [d, r, c] = q.front();  q.pop();
        if (r == R - 1 && c == C - 1) return d;
        
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                // 遍历8个方向
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= R || nc < 0 || nc >= C 
                    || grid[nr][nc] || visited[nr][nc]) continue;
                q.push({d + 1, nr, nc});
                visited[nr][nc] = true;
            }
        }
    }
    return -1;
}