สมมติว่าเรามีกราฟไม่มีทิศทางมีน้ำหนักเชื่อมต่อกัน กราฟมี n โหนดตั้งชื่อ 1 ถึง n เส้นทางจากเริ่มต้นถึงสิ้นสุดคือลำดับโหนด [z0, z1, z2, ..., zk] โดย z0 เป็นโหนดเริ่มต้น zk เป็นโหนดสิ้นสุด และมีเส้นขอบระหว่าง zi และ zi+1 โดย 0 <= i <= k-1 ระยะทางของเส้นทางคือผลรวมของค่าน้ำหนักบนเส้นขอบของเส้นทาง ให้ dist(x) แทนระยะทางสั้นที่สุดจากโหนด n และโหนด x เส้นทางจำกัด (restricted path) คือเส้นทางพิเศษที่ยังสอดคล้องกับ dist(zi) > dist(zi+1) โดย 0 <= i <= k-1 เราต้องหาจำนวนเส้นทางจำกัดจากโหนด 1 ถึงโหนด n ถ้าคำตอบใหญ่เกินไป return คำตอบ modulo 10^9 + 7
เช่น ถ้าอินพุตเป็นดังภาพ ผลลัพธ์จะเป็น 3 เพราะมีเส้นทางจำกัดสามเส้นทาง: (1,2,5), (1,2,3,5), (1,3,5)
วิธีแก้ปัญหา
- graph := adjacency list ของกราฟจาก edge list ที่กำหนด
- paths := อาร์เรย์ขนาด (n+1) เติม 0
- paths[n] := 1
- dists := อาร์เรย์ขนาด (n+1) เติม -1
- q := คิว แทรก (0, 0) เริ่มต้น
- while q ไม่ว่าง:
- (dist, node) := องค์ประกอบหน้าคิวและลบออก
- ถ้า dists[node] ไม่เท่ากับ -1: ข้ามรอบถัดไป
- dists[node] := dist
- สำหรับแต่ละโหนดติด v และน้ำหนัก w ของ graph[node]:
- ถ้า dists[v] เท่ากับ -1: แทรก (dist + w, v) ลง q
- มิฉะนั้นเมื่อ dists[v] < dists[node]: paths[node] := paths[node] + paths[v]
- ถ้า node เท่ากับ 1: return paths[node] mod 10^9+7
- return 0
ตัวอย่าง
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))
อินพุต
5,[(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]
เอาต์พุต
3
