class Solution:
# 朴素dijkstra，适用于稠密图
def countPaths1(self, n: int, roads: List[List[int]]) -> int:
g = [[inf for _ in range(n)] for _ in range(n)] # 邻接矩阵
for x, y, d in roads:
g[x][y] = d
g[y][x] = d
dis = [inf] * n
dis[0] = 0
f = [0] * n
f[0] = 1
done = [False] * n
while True:
x = -1
for i, ok in enumerate(done):
if not ok and (x < 0 or dis[i] < dis[x]):
x = i
if x == n - 1:
# 不可能找到比 dis[-1] 更短，或者一样短的最短路了（注意本题边权都是正数）
return f[-1]
done[x] = True # 最短路长度已确定（无法变得更小）
dx = dis[x]
for y, d in enumerate(g[x]): # 尝试更新 x 的邻居的最短路
new_dis = dx + d
if new_dis < dis[y]:
# 就目前来说，最短路必须经过 x
dis[y] = new_dis
f[y] = f[x]
elif new_dis == dis[y]:
# 和之前求的最短路一样长
f[y] = (f[y] + f[x]) % 1_000_000_007
# 堆优化dijkstra算法，适用于稀疏图
def countPaths(self, n: int, roads: List[List[int]]) -> int:
g = [[] for _ in range(n)] # 邻接表
for x, y, d in roads:
g[x].append((y, d))
g[y].append((x, d))
dis = [inf] * n
dis[0] = 0
f = [0] * n
f[0] = 1
h = [(0, 0)]
while True:
dx, x = heappop(h)
if x == n - 1:
# 不可能找到比 dis[-1] 更短，或者一样短的最短路了（注意本题边权都是正数）
return f[-1]
if dx > dis[x]:
continue
for y, d in g[x]: # 尝试更新 x 的邻居的最短路
new_dis = dx + d
if new_dis < dis[y]:
# 就目前来说，最短路必须经过 x
dis[y] = new_dis
f[y] = f[x]
heappush(h, (new_dis, y))
elif new_dis == dis[y]:
# 和之前求的最短路一样长
f[y] = (f[y] + f[x]) % 1_000_000_007
class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
mod = 10**9 + 7
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for x, y, z in roads:
dist[x][y] = dist[y][x] = z
# Floyd 算法求解最短路
# 完成后，dist[0][i] 即为正文部分的 dist[i]
# for k in range(n):
# for i in range(n):
# for j in range(n):
# dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# Dijkstra 算法求解最短路
# 完成后，dist[0][i] 即为正文部分的 dist[i]
seen = set()
for _ in range(n - 1):
u = None
for i in range(n):
if i not in seen and (not u or dist[0][i] < dist[0][u]):
u = i
seen.add(u)
for i in range(n):
dist[0][i] = min(dist[0][i], dist[0][u] + dist[u][i])
# 构造图 G
g = defaultdict(list)
for x, y, z in roads:
if dist[0][y] - dist[0][x] == z:
g[x].append(y)
elif dist[0][x] - dist[0][y] == z:
g[y].append(x)
@cache
def dfs(u: int) -> int:
if u == n - 1:
return 1
ret = 0
for v in g[u]:
ret += dfs(v)
return ret % mod
ans = dfs(0)
dfs.cache_clear()
return ans
class Solution {
static class Edge {
int to;
long len;
Edge(int _to, long _len) {
to = _to;
len = _len;
}
}
List<Edge>[] graph;
// INF 不能是经典的 0x3f3f3f3f，要变大！
final long INF = (Long.MAX_VALUE >> 1) - (long)1e5;
final int MOD = (int)1e9 + 7;
private int dijkstra(int ed) {
PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> Long.compare(a.len, b.len));
boolean[] vis = new boolean[ed];
long[] dist = new long[ed];
int[] cnt = new int[ed];
pq.offer(new Edge(0, 0));
Arrays.fill(dist, INF);
dist[0] = 0;
cnt[0] = 1;
while (!pq.isEmpty()) {
var u = pq.poll().to;
if (vis[u]) {
continue;
}
vis[u] = true;
for (var next : graph[u]) {
int v = next.to;
long w = next.len;
if (dist[v] > dist[u] + w) {
// 新的最短路继承前驱的最短路径条数
cnt[v] = cnt[u];
dist[v] = dist[u] + w;
pq.offer(new Edge(v, dist[v]));
} else if (dist[v] == dist[u] + w) {
// 相同的最短路走法（指走到 v）则进行累加
// 不要忘记取模
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
}
}
return cnt[ed - 1];
}
public int countPaths(int n, int[][] roads) {
graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (var p : roads) {
// 翻译很迷，其实完全可以翻译成无向图
int u = p[0], v = p[1], w = p[2];
graph[u].add(new Edge(v, w));
graph[v].add(new Edge(u, w));
}
return dijkstra(n);
}
}
func countPaths(n int, roads [][]int) (ans int) {
g := make([][]int, n)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = 1e18
}
}
for _, r := range roads {
v, w, wt := r[0], r[1], r[2]
g[v][w] = wt
g[w][v] = wt
}
// 求 0 到其余点的最短路
d := make([]int, n)
for i := range d {
d[i] = 1e18
}
d[0] = 0
used := make([]bool, n)
for {
v := -1
for w, u := range used {
if !u && (v < 0 || d[w] < d[v]) {
v = w
}
}
if v < 0 {
break
}
used[v] = true
for w, wt := range g[v] {
if newD := d[v] + wt; newD < d[w] {
d[w] = newD
}
}
}
// 最短路构成了一个 DAG，这里不需要建一个新图，直接根据距离来判断每条边是否在 DAG 上
// 计算 DAG 的入度数组
deg := make([]int, n)
for v, r := range g {
for w, wt := range r {
if d[v]+wt == d[w] { // 这条边在 DAG 上
deg[w]++
}
}
}
// 在 DAG 上跑拓扑排序
dp := make([]int, n) // dp[i] 表示 0 到 i 的最短路个数
dp[0] = 1
q := []int{0}
for len(q) > 0 {
v := q[0]
q = q[1:]
for w, wt := range g[v] {
if d[v]+wt == d[w] { // 这条边在 DAG 上
dp[w] = (dp[w] + dp[v]) % (1e9 + 7)
if deg[w]--; deg[w] == 0 {
q = append(q, w)
}
}
}
}
return dp[n-1]
}
