Medium
题目描述
你在一个由 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 算法求出从起点 0 到所有节点的最短距离。
构建最短路径DAG：只保留满足
dist[u] + weight = dist[v]的边，这些边构成了一个有向无环图(DAG)，其中所有路径都是最短路径。动态规划计数：在DAG上使用动态规划计算路径数量。设
ways[i]表示从起点到节点 i 的最短路径数量，则ways[v] += ways[u]（当存在从u到v的最短路径边时）。
算法流程：
- 首先建图，使用邻接表存储
- 用Dijkstra算法求最短距离
- 遍历所有边，只保留在最短路径上的边
- 在新图上用BFS/DFS + 记忆化搜索计算路径数
时间复杂度主要由Dijkstra算法决定，为 O(E log V)，其中 E 是边数，V 是节点数。
代码实现
class Solution {
public:
int countPaths(int n, vector<vector<int>>& roads) {
const int MOD = 1e9 + 7;
// Build graph
vector<vector<pair<int, long long>>> graph(n);
for (auto& road : roads) {
int u = road[0], v = road[1];
long long time = road[2];
graph[u].push_back({v, time});
graph[v].push_back({u, time});
}
// Dijkstra to find shortest distances
vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
// Build DAG with shortest path edges only
vector<vector<int>> dag(n);
for (auto& road : roads) {
int u = road[0], v = road[1];
long long time = road[2];
if (dist[u] + time == dist[v]) {
dag[u].push_back(v);
} else if (dist[v] + time == dist[u]) {
dag[v].push_back(u);
}
}
// Count paths using DP
vector<long long> ways(n, 0);
ways[0] = 1;
vector<int> indegree(n, 0);
for (int u = 0; u < n; u++) {
for (int v : dag[u]) {
indegree[v]++;
}
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : dag[u]) {
ways[v] = (ways[v] + ways[u]) % MOD;
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
return ways[n - 1];
}
};
class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
MOD = 10**9 + 7
# Build graph
graph = [[] for _ in range(n)]
for u, v, time in roads:
graph[u].append((v, time))
graph[v].append((u, time))
# Dijkstra to find shortest distances
dist = [float('inf')] * n
dist[0] = 0
pq = [(0, 0)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
# Build DAG with shortest path edges only
dag = [[] for _ in range(n)]
for u, v, time in roads:
if dist[u] + time == dist[v]:
dag[u].append(v)
elif dist[v] + time == dist[u]:
dag[v].append(u)
# Count paths using DP with topological sort
indegree = [0] * n
for u in range(n):
for v in dag[u]:
indegree[v] += 1
ways = [0] * n
ways[0] = 1
queue = deque()
for i in range(n):
if indegree[i] == 0:
queue.append(i)
while queue:
u = queue.popleft()
for v in dag[u]:
ways[v] = (ways[v] + ways[u]) % MOD
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return ways[n - 1]
public class Solution {
public int CountPaths(int n, int[][] roads) {
const int MOD = 1000000007;
// Build graph
List<(int, long)>[] graph = new List<(int, long)>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<(int, long)>();
}
foreach (var road in roads) {
int u = road[0], v = road[1];
long time = road[2];
graph[u].Add((v, time));
graph[v].Add((u, time));
}
// Dijkstra to find shortest distances
long[] dist = new long[n];
for (int i = 0; i < n; i++) {
dist[i] = long.MaxValue;
}
dist[0] = 0;
var pq = new PriorityQueue<(long dist, int node), long>();
pq.Enqueue((0, 0), 0);
while (pq.Count > 0) {
var (d, u) = pq.Dequeue();
if (d > dist[u]) continue;
foreach (var (v, w) in graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.Enqueue((dist[v], v), dist[v]);
}
}
}
// Build DAG with shortest path edges only
List<int>[] dag = new List<int>[n];
for (int i = 0; i < n; i++) {
dag[i] = new List<int>();
}
foreach (var road in roads) {
int u = road[0], v = road[1];
long time = road[2];
if (dist[u] + time == dist[v]) {
dag[u].Add(v);
} else if (dist[v] + time == dist[u]) {
dag[v].Add(u);
}
}
// Count paths using DP with topological sort
int[] indegree = new int[n];
for (int u = 0; u < n; u++) {
foreach (int v in dag[u]) {
indegree[v]++;
}
}
long[] ways = new long[n];
ways[0] = 1;
var queue = new Queue<int>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.Enqueue(i);
}
}
while (queue.Count > 0) {
int u = queue.Dequeue();
foreach (int v in dag[u]) {
ways[v] = (ways[v] + ways[u]) % MOD;
indegree[v]--;
if (indegree[v] == 0) {
queue.Enqueue(v);
}
}
}
return (int)ways[n - 1];
}
}
var countPaths = function(n, roads) {
const MOD = 1e9 + 7;
const graph = Array(n).fill().map(() => []);
for (const [u, v, time] of roads) {
graph[u].push([v, time]);
graph[v].push([u, time]);
}
const dist = Array(n).fill(Infinity);
const ways = Array(n).fill(0);
const pq = [[0, 0]];
dist[0] = 0;
ways[0] = 1;
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift();
if (d > dist[u]) continue;
for (const [v, time] of graph[u]) {
const newDist = dist[u] + time;
if (newDist < dist[v]) {
dist[v] = newDist;
ways[v] = ways[u];
pq.push([newDist, v]);
} else if (newDist === dist[v]) {
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
return ways[n - 1];
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(E log V) | Dijkstra算法复杂度，E为边数，V为节点数 |
| 空间复杂度 | O(V + E) | 图的存储空间和辅助数组空间 |