Á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\mathrm{\_}path[]$,$cnt\mathrm{\_}path[i]$ là số cách bay ít chi phí nhất từ quốc gia $1$ tới quốc gia $i$.

$min\mathrm{\_}flt[]$, $min\mathrm{\_}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\mathrm{\_}flt[]$, $max\mathrm{\_}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\mathrm{\_}path[i]=cnt\mathrm{\_}path[j]$
• $max\mathrm{\_}flt[i]=max\mathrm{\_}flt[j]+1$
• $min\mathrm{\_}flt[i]=min\mathrm{\_}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\mathrm{\_}path[i]+=cnt\mathrm{\_}path[j]$
• $cnt\mathrm{\_}path[i]mod1000000007$
• $max\mathrm{\_}flt[i]=max(max\mathrm{\_}flt[i],max\mathrm{\_}flt[j]+1)$
• $min\mathrm{\_}flt[i]=min(min\mathrm{\_}flt[i],min\mathrm{\_}flt[j]+1)$

$dist[n],cnt\mathrm{\_}path[n],min\mathrm{\_}flt[n],max\mathrm{\_}flt[n]$ là kết quả của bài toán.