Unique Paths to Go Home - Google Top Interview Questions

                        Solution in C++ :

long long dp[100005];
long long dist[100005];
int n;
vector<pair<int, int>> edges[100005];
int solve(vector<vector<int>>& graph) {
    // begin graph initialization
    n = 0;
    for (auto& edge : graph) {
        n = max(n, edge[0]);
        n = max(n, edge[1]);
    }
    n++;
    for (int i = 0; i < n; i++) edges[i].clear();
    for (auto& edge : graph) {
        edges[edge[0]].emplace_back(edge[1], edge[2]);
        edges[edge[1]].emplace_back(edge[0], edge[2]);
    }
    // end graph initialization

    // begin dijkstra
    for (int i = 0; i < n; i++) dist[i] = 1e18;
    dist[n - 1] = 0;
    priority_queue<pair<long long, long long>> q;
    q.emplace(0, n - 1);
    vector<int> orderv;
    while (q.size()) {
        auto [w, v] = q.top();
        q.pop();
        w *= -1;
        if (dist[v] != w) continue;
        orderv.push_back(v);
        for (auto edge : edges[v]) {
            if (dist[edge.first] > dist[v] + edge.second) {
                dist[edge.first] = dist[v] + edge.second;
                q.emplace(-dist[edge.first], edge.first);
            }
        }
    }
    // end dijkstra

    // begin path counting
    for (int i = 0; i < n; i++) dp[i] = 0;
    dp[n - 1] = 1;
    const int MOD = 1000000007;
    for (int currv : orderv) {
        for (auto& edge : edges[currv]) {
            if (dist[edge.first] < dist[currv]) {
                dp[currv] += dp[edge.first];
                dp[currv] %= MOD;
            }
        }
    }
    // end path counting
    return dp[0];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[][] edges) {
        int N = 0;
        for (int[] edge : edges) N = Math.max(N, Math.max(edge[0], edge[1]));
        N++;
        ArrayList<State>[] graph = new ArrayList[N];
        for (int i = 0; i < N; i++) graph[i] = new ArrayList<State>();
        for (int[] e : edges) {
            long w = (long) e[2];
            graph[e[0]].add(new State(e[1], w));
            graph[e[1]].add(new State(e[0], w));
        }

        // Dijkstra's Algorithm
        long[] distances = new long[N];
        Arrays.fill(distances, Long.MAX_VALUE);
        distances[N - 1] = 0L;
        PriorityQueue<State> pq = new PriorityQueue<State>();
        State s = new State(N - 1, 0L);
        pq.add(s);
        while (!pq.isEmpty()) {
            s = pq.poll();
            for (State e : graph[s.node]) {
                if (distances[e.node] > distances[s.node] + e.dist) {
                    distances[e.node] = distances[s.node] + e.dist;
                    pq.add(new State(e.node, distances[e.node]));
                }
            }
        }
        State[] vals = new State[N];
        for (int i = 0; i < N; i++) vals[i] = new State(i, distances[i]);
        Arrays.sort(vals);

        long[] ans = new long[N];
        ans[N - 1] = 1L;
        for (int i = 1; i < N; i++) {
            int u = vals[i].node;
            for (State e : graph[u]) {
                int v = e.node;
                if (distances[u] > distances[v])
                    ans[u] = (ans[u] + ans[v]) % 1000000007;
            }
        }
        return (int) ans[0];
    }

    static class State implements Comparable<State> {
        int node;
        long dist;
        public State(int n, long d) {
            node = n;
            dist = d;
        }

        public int compareTo(State s) {
            return Long.compare(dist, s.dist);
        }
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, edges):
        MOD = 10 ** 9 + 7

        graph = defaultdict(dict)
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w

        # Find distance from home to nodes with Dijkstra
        home = max(graph)
        dist = defaultdict(lambda: float("inf"))
        dist[home] = 0
        pq = [[0, home]]
        while pq:
            d, node = heappop(pq)
            if dist[node] < d:
                continue

            for nei, w in graph[node].items():
                if d + w < dist[nei]:
                    heappush(pq, [d + w, nei])
                    dist[nei] = d + w

        # DP on topological order
        nodes = sorted(graph, key=dist.__getitem__)
        dp = defaultdict(int)
        dp[home] = 1
        for u in nodes:
            for v in graph[u]:
                if dist[v] > dist[u]:
                    dp[v] += dp[u]
                    dp[v] %= MOD

        return dp[0]