SSSP + DP

The third question of this week’s LeetCode contest is a strandard SSSP (Single Source Shortest Path) problem with some variations. We need further use DP (DFS + memo) to get the results.

Problem

1786. Number of Restricted Paths From First to Last Node

Explanation

Find the shortest distance to node n by using SSSP algorithm.

The classical SSSP algorithm when there is no negative weigths is dijkstra algorithm. We also have an alternative which is named SPFA(Shortest Path “Faster” Algorithm).

Everyone should hear about Dijkstra if you are computer science student or professionals. For the SPFA, it is well know in the Chinese computer science community. The algorithm is published in Chinese in 1994 by Duan.

Code

typedef vector<int> vi;
typedef pair<int, int> ii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int dp[20010];
class Solution {
public:
    vector<vector<ii>> AL;
    vi dist;
    int n;
    // dfs with memo to get the result
    int dfs(int i) {
        if (i == n) return 1;
        if (dp[i]!=INF) return dp[i];
        int ret = 0;
        for (auto &[v, w]: AL[i]) {
            if (dist[i] > dist[v]) {
                auto this_ret = dfs(v);
                ret += this_ret;
                if (ret >= mod) ret %= mod; 
            }
        }
        return dp[i] = ret; 
    }
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        this->n = n;
        // standard Dijkstra
        memset(dp, 0x3f, sizeof dp);
        vector<vector<ii>> AL(n+1, vector<ii>());
        for (auto &e: edges) {
            int u = e[0], v = e[1], w = e[2];
            AL[u].emplace_back(v, w);
            AL[v].emplace_back(u, w);
        }
        this->AL = AL;
        int s = n;
        vi dist(n + 1, INF);dist[s] = 0;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.emplace(0, s);
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto &[v, w]: AL[u]) {
                if (dist[u] + w >= dist[v]) continue;
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
        this->dist = dist;
        return dfs(1);
    }
};

Thanks for reading.