這題我第一次看起來覺得很複雜,但是仔細想一下之後就會發現其實沒有很難解,只是將 Dijkstra 搭配上 DP 就可以處理掉了
然後在進行 Dijkstra 的時候要同時追蹤下面四個東西
dis[]
routes[]
minf[]
maxf[]
對於每個節點 ,我們都會考慮他的所有權重為 的鄰居 ,當我們可以鬆弛邊 (dis[v] > dis[u] + w)時,就將變數的值更改成下面這樣
dis[v]
= dis[u] + w
routes[v]
= routes[u]
minf[v]
= minf[u] + 1
maxf[v]
= maxf[v] + 1
但跟平常的 Dijkstra 不一樣的是我們還必須考慮到 dis[v] = dis[u] + w 的情況(因為你不會知道當前是不是最段距離),所以當 dis[v] = dis[u] + w 成立時,我們將值更新成下變這樣
dis[v]
不更新routes[v]
= ( routes[v] + routes[u] ) % Mod
➨ 這邊記得取模minf[v]
= min( minf[v], minf[u] + 1 )
maxf[v]
= max( maxf[v], maxf[u] + 1 )