Chương trình tìm số đường đi bị hạn chế từ đỉnh đầu đến đỉnh cuối trong Python

Cho đồ thị vô hướng có trọng số, liên thông, n đỉnh 1..n. Đường đi từ start đến end là dãy [z0, z1, ..., zk] có cạnh giữa zi và zi+1. Khoảng cách đường = tổng trọng số. dist(x) = khoảng cách ngắn nhất từ n đến x. Đường bị hạn chế (restricted path) thỏa dist(zi) > dist(zi+1). Tìm số đường bị hạn chế từ 1 đến n, modulo 10^9+7.

Ví dụ: đầu vào như hình, đầu ra = 3 (3 đường: (1,2,5), (1,2,3,5), (1,3,5)).

Giải pháp

Dijkstra từ đỉnh n tính dist(), sau đó DP đếm đường đi giảm dần dist:

• graph := danh sách kề từ edge list
• paths := mảng n+1 điền 0, paths[n] := 1
• dists := mảng n+1 điền -1
• q := priority queue, push (0, n)
• Khi q không rỗng:
  • dist, node := heappop(q)
  • Nếu dists[node] != -1: continue
  • dists[node] := dist
  • Với mỗi v, w kề node:
    • Nếu dists[v] == -1: heappush(q, (dist+w, v))
    • Ngược lại nếu dists[v] < dists[node]: paths[node] += paths[v]
  • Nếu node == 1: trả về paths[node] % (10^9+7)
• Trả về 0

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

from collections import defaultdict
from heapq import heappop, heappush

def solve(n, edges):
    graph = defaultdict(dict)
    for u, v, w in edges:
        graph[u][v] = w
        graph[v][u] = w
    paths = [0] * (n+1)
    paths[n] = 1
    dists = [-1] * (n+1)
    q = [(0, n)]
    while q:
        dist, node = heappop(q)
        if dists[node] != -1:
            continue
        dists[node] = dist
        for v, w in graph[node].items():
            if dists[v] == -1:
                heappush(q, (dist + w, v))
            elif dists[v] < dists[node]:
                paths[node] += paths[v]
        if node == 1:
            return paths[node] % (10**9 + 7)
    return 0

n = 5
edges = [(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]
print(solve(n, edges))

Đầu vào

5,[(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]

Đầu ra

3