Áp dụng thuật toán Dijkstra, ngoài mảng \(dist[]\) lưu chi phí ngắn nhất xuất phát từ quốc gia \(1\) ta lưu thêm các mảng:

\(cnt\_path[]\),\(cnt\_path[i]\) là số cách bay ít chi phí nhất từ quốc gia \(1\) tới quốc gia \(i\).

\(min\_flt[]\), \(min\_flt[i]\) là số chuyến bay tối thiểu với tổng chi phí là ít nhất tới quốc gia \(i\).

\(max\_flt[]\), \(max\_flt[i]\) là số chuyến bay tối đa với tổng chi phí là ít nhất tới quốc gia \(i\).

Mỗi khi cập nhật \(dist[i]\) từ đỉnh \(j\), cập nhật các mảng trên như sau:

• \(cnt\_path[i] = cnt\_path[j]\)
• \(max\_flt[i] = max\_flt[j] + 1\)
• \(min\_flt[i] = min\_flt[j] + 1\)
• (Số cách bay tối ưu tới thành phố \(i\) bằng số cách bay tối ưu tới thành phố \(j\), số chuyến bay tới \(i\) bằng số chuyến bay tới \(j\) thêm \(1\))

Ngoài ra nếu \(dist[i] = dist[j]\) ta cũng phải cập nhật lại các mảng:

• \(cnt\_path[i] += cnt\_path[j]\)
• \(cnt\_path[i]\:mod\:1000000007\)
• \(max\_flt[i]=max(max\_flt[i], max\_flt[j] + 1)\)
• \(min\_flt[i]=min(min\_flt[i], min\_flt[j] + 1)\)

\(dist[n], cnt\_path[n], min\_flt[n], max\_flt[n]\) là kết quả của bài toán.