LC.P1976[到达目的地的方案数]

方法一：dijkstra+拓扑排序+dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {

    private static final int MOD = (int) 1e9 + 7;
    private static final long INF = Long.MAX_VALUE >> 2;
    int n;
    long[] dist;
    int[][] g;
    int[] in;
    boolean[] visited;

    public int countPaths(int n, int[][] roads) {
        this.n = n;
        g = new int[n][n];
        dist = new long[n];
        in = new int[n];
        visited = new boolean[n];
        for (int[] road : roads) {
            int a = road[0], b = road[1], w = road[2];
            g[a][b] = g[b][a] = w;
        }
        dijkstra();
        for (int[] road : roads) {
            int a = road[0], b = road[1], w = road[2];
            g[a][b] = g[b][a] = 0;
            if (dist[a] + w == dist[b]) {
                g[a][b] = w;
                ++in[b];
            } else if (dist[b] + w == dist[a]) {
                g[b][a] = w;
                ++in[a];
            }
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            if (in[i] == 0) queue.offer(i);
        }
        int[] f = new int[n];
        f[0] = 1;
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int i = 0; i < n; ++i) {
                if (g[x][i] == 0) continue;
                f[i] += f[x];
                f[i] %= MOD;
                if (--in[i] == 0) queue.offer(i);
            }
        }
        return f[n - 1];
    }

    private void dijkstra() {
        Arrays.fill(dist, INF);
        dist[0] = 0L;
        for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && (k == -1 || dist[j] < dist[k])){
                    k = j;
                }
            }
            visited[k] = true;
            for (int j = 0; j < n; ++j) {
                if (g[k][j] == 0) continue;
                dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
            }
        }
    }
}
  • 时间复杂度：首次建图复杂度为$O(m)$，$Dijkstra$求最短路复杂度为$O(n^2)$，再次建图复杂度为$O(m)$，拓扑排序统计方案数复杂度为$(m + n)$，整体复杂度为$O(n^2 + m)$
  • 空间复杂度：$O(n^2)$