Tutorial — Hệ Thống Kênh

Để tìm khoảng cách ngắn nhất và số lượng đường đi ngắn nhất từ nút $1$ đến nút $N$, hãy xem xét thứ tự các nút được xử lý khi khoảng cách đến chúng đã đạt giá trị tối ưu.

Gọi $dist[u]$ là độ dài ngắn nhất và $ways[u]$ là số lượng đường đi ngắn nhất từ $1$ đến $u$. Khi xét kênh từ $u$ đến $v$ độ dài $L$, nếu $dist[u] + L < dist[v]$, ta cập nhật $dist[v] = dist[u] + L$ và gán $ways[v] = ways[u]$; nếu $dist[u] + L = dist[v]$, ta cộng dồn $ways[v] = ways[v] + ways[u]$.

Sử dụng thuật toán Dijkstra với hàng đợi ưu tiên để lan truyền khoảng cách $dist$ và đếm số đường đi $ways$ đồng thời. Nếu sau khi hoàn tất mà $dist[N]$ bằng giá trị vô cùng ban đầu, kết quả cần in ra là $0$ $0$.