正負反転ダイクストラ(到達判定) - Githubissues

tipstar0125 / atcoder

atcoder

6 stars 0 forks source link

正負反転ダイクストラ(到達判定) #25

Open tipstar0125 opened 7 months ago

tipstar0125 commented 7 months ago

https://atcoder.jp/contests/abc305/tasks/abc305_e https://atcoder.jp/contests/abc309/tasks/abc309_e

tipstar0125 commented 7 months ago

distは-1で初期化
多始点ダイクストラ
正負反転なので、Reverseは不要
dist[pos]-1>dist[next]でQを更新（-1しても、大きければ、それで上塗りして、到達できる範囲が増える）