连通图最小路径个数

LC1976. 到达目的地的方案数

你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。

给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。

请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

示例 1：

输入：n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出：4
解释：从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为：
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

示例 2：

输入：n = 2, roads = [[1,0,10]]
输出：1
解释：只有一条从路口 0 到路口 1 的路，花费 10 分钟。

提示：

• 1 <= n <= 200
• n - 1 <= roads.length <= n * (n - 1) / 2
• roads[i].length == 3
• 0 <= ui, vi <= n - 1
• 1 <= timei <= 109
• ui != vi
• 任意两个路口之间至多有一条路。
• 从任意路口出发，你能够到达其他任意路口。

解法一

Dijkstra算法，一遍求最短路径，一边计算路径的个数，令f[e]表示点0到e的最短路径个数，显然f[0]等于1，假设到点e最短路径的上一个点有两个分别是u和v，那么f[e] = f[u] + f[v],若只有一个u的话,f[e] = f[u],根据这点性质，加上Dijkstra遍历的特点，很容易就可以想到在Dijkstra在进行距离转移变化时，若相等就加，若小于就覆盖。

class Solution {
    public int countPaths(int n, int[][] roads) {
        int mod = (int) (1e9 + 7);
        long[] d = new long[n];
        Arrays.fill(d, Long.MAX_VALUE);
        d[0] = 0;
        int[] f = new int[n];
        f[0] = 1;
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var road : roads) {
            int u = road[0], v = road[1], t = road[2];
            g[u].add(new int[] {v, t});
            g[v].add(new int[] {u, t});
        }
        PriorityQueue<long[]> heap = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
        boolean[] vis = new boolean[n];
        heap.add(new long[] {0, 0});
        while (!heap.isEmpty()) {
            long[] poll = heap.poll();
            int e = (int) poll[0];
            long t = poll[1];
            if (vis[e]) continue;
            if (e == n - 1) return f[n - 1];  //这里直接返回就行，绝对没有相等的距离在后面，因为heap会把距离更小的先遍历
            for (var it : g[e]) {
                int ee = it[0], va = it[1];
                if (va + t < d[ee]) {
                    f[ee] = f[e];
                    d[ee] = va + t;
                    heap.add(new long[] {ee, d[ee]});
                } else if (va + t == d[ee]) {
                    f[ee] = (f[ee] + f[e]) % mod;
                }
            }
            vis[e] = true;
        }
        return f[n - 1];
    }
}

解法二

Dijkstra+TopSort。

经过Dijkstra一遍过后已经得知每个点距离0的距离，假设有点u、v,d[u] = d[v] + g[v][u]，那么对于求最短距离而言u -> v这条边已经没有用了，同时其他的点到v的路径也没用了，因此可以删去一些无用边。

示例一去除无效边后的图

这样重新建图后就可以使用topsort遍历一遍即可求出f[n - 1]

class Solution {
    public int countPaths(int n, int[][] roads) {

        long[][] g = new long[n][n];
        for (var gg : g) Arrays.fill(gg, -1);
        for (var road : roads) {
            int u = road[0], v = road[1], t = road[2];
            g[u][v] = g[v][u] = t;
        }
        long[] d = new long[n];
        Arrays.fill(d, Long.MAX_VALUE / 2);
        d[0] = 0;
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 0; j < n; j++) {
                if (!vis[j] && (t == -1 || d[t] > d[j])) t = j;
            }
            vis[t] = true;
            for (int j = 0; j < n; j++) {
                if (g[j][t] != -1) {
                    d[j] = Math.min(d[j], d[t] + g[j][t]);
                }
            }
        }
        for (var gg : g) Arrays.fill(gg, -1);
        int[] deg = new int[n];
        long[] f = new long[n];
        f[0] = 1;
        for (var road : roads) {
            int u = road[0], v = road[1], t = road[2];
            if (d[u] == d[v] + t) {
                g[v][u] = t;
                deg[u]++;
            } else if (d[v] == d[u] + t) {
                g[u][v] = t;
                deg[v]++;
            }
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (deg[i] == 0) queue.add(i);
        }
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v = 0; v < n; v++) {
                if (g[u][v] != -1) {
                    f[v] = (f[v] + f[u]) % (long) (1e9 + 7);
                    if (--deg[v] == 0) {
                        queue.add(v);
                    }
                }
                
            }
        }
        return (int) f[n - 1];

    }
}