Skip to content

Latest commit

 

History

History
255 lines (217 loc) · 7.48 KB

README.md

File metadata and controls

255 lines (217 loc) · 7.48 KB
Raw

1976. 到达目的地的方案数

English Version

题目描述

你在一个城市里，城市由 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 算法

在求最短路的过程中顺便记录到达某个点最短路径的方案数。松弛优化时，如果发现有更优的路径，则方案数也赋值最优路径的前驱的方案数。如果发现与最优的路径长度相同，则累加当前前驱的方案数。

由于图有可能非常稠密，所以采用朴素的 Dijkstra 算法。

时间复杂度 $O(n^2)$。

注意：最短路的长度可能会 超过 32 位整数的范围。

Python3

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        INF = inf
        MOD = 10**9 + 7
        g = [[INF] * n for _ in range(n)]
        for u, v, t in roads:
            g[u][v] = t
            g[v][u] = t
        g[0][0] = 0
        dist = [INF] * n
        w = [0] * n
        dist[0] = 0
        w[0] = 1
        vis = [False] * n
        for _ in range(n):
            t = -1
            for i in range(n):
                if not vis[i] and (t == -1 or dist[i] < dist[t]):
                    t = i
            vis[t] = True
            for i in range(n):
                if i == t:
                    continue
                ne = dist[t] + g[t][i]
                if dist[i] > ne:
                    dist[i] = ne
                    w[i] = w[t]
                elif dist[i] == ne:
                    w[i] += w[t]
        return w[-1] % MOD

Java

class Solution {
    private static final long INF = Long.MAX_VALUE / 2;
    private static final int MOD = (int) 1e9 + 7;

    public int countPaths(int n, int[][] roads) {
        long[][] g = new long[n][n];
        long[] dist = new long[n];
        long[] w = new long[n];
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(g[i], INF);
            Arrays.fill(dist, INF);
        }
        for (int[] r : roads) {
            int u = r[0], v = r[1], t = r[2];
            g[u][v] = t;
            g[v][u] = t;
        }
        g[0][0] = 0;
        dist[0] = 0;
        w[0] = 1;
        for (int i = 0; i < n; ++i) {
            int t = -1;
            for (int j = 0; j < n; ++j) {
                if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            vis[t] = true;
            for (int j = 0; j < n; ++j) {
                if (j == t) {
                    continue;
                }
                long ne = dist[t] + g[t][j];
                if (dist[j] > ne) {
                    dist[j] = ne;
                    w[j] = w[t];
                } else if (dist[j] == ne) {
                    w[j] = (w[j] + w[t]) % MOD;
                }
            }
        }
        return (int) w[n - 1];
    }
}

C++

typedef long long ll;

class Solution {
public:
    const ll INF = LLONG_MAX / 2;
    const int MOD = 1e9 + 7;

    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<ll>> g(n, vector<ll>(n, INF));
        vector<ll> dist(n, INF);
        vector<ll> w(n);
        vector<bool> vis(n);
        for (auto& r : roads) {
            int u = r[0], v = r[1], t = r[2];
            g[u][v] = t;
            g[v][u] = t;
        }
        g[0][0] = 0;
        dist[0] = 0;
        w[0] = 1;
        for (int i = 0; i < n; ++i) {
            int t = -1;
            for (int j = 0; j < n; ++j) {
                if (!vis[j] && (t == -1 || dist[t] > dist[j])) t = j;
            }
            vis[t] = true;
            for (int j = 0; j < n; ++j) {
                if (t == j) continue;
                ll ne = dist[t] + g[t][j];
                if (dist[j] > ne) {
                    dist[j] = ne;
                    w[j] = w[t];
                } else if (dist[j] == ne)
                    w[j] = (w[j] + w[t]) % MOD;
            }
        }
        return w[n - 1];
    }
};

Go

func countPaths(n int, roads [][]int) int {
	const inf = math.MaxInt64 / 2
	const mod = int(1e9) + 7
	g := make([][]int, n)
	dist := make([]int, n)
	w := make([]int, n)
	vis := make([]bool, n)
	for i := range g {
		g[i] = make([]int, n)
		dist[i] = inf
		for j := range g[i] {
			g[i][j] = inf
		}
	}
	for _, r := range roads {
		u, v, t := r[0], r[1], r[2]
		g[u][v], g[v][u] = t, t
	}
	g[0][0] = 0
	dist[0] = 0
	w[0] = 1
	for i := 0; i < n; i++ {
		t := -1
		for j := 0; j < n; j++ {
			if !vis[j] && (t == -1 || dist[t] > dist[j]) {
				t = j
			}
		}
		vis[t] = true
		for j := 0; j < n; j++ {
			if j == t {
				continue
			}
			ne := dist[t] + g[t][j]
			if dist[j] > ne {
				dist[j] = ne
				w[j] = w[t]
			} else if dist[j] == ne {
				w[j] = (w[j] + w[t]) % mod
			}
		}
	}
	return w[n-1]
}

...