C - Path Intersection Editorial by nyoguta
別解答えは \(\{\text{dist}(s,j)+\text{dist}(j,t)-\text{dist}(s,t)\}/2+1\) なので(下図参照) \(s\) と \(t\) からそれぞれ単一始点最短路をすれば求まります。
s
|
o
|
o ＝ o ＝ o ＝ o ＝ o ＝ j
|
o
|
t
posted:
last update:
答えは \(\{\text{dist}(s,j)+\text{dist}(j,t)-\text{dist}(s,t)\}/2+1\) なので(下図参照) \(s\) と \(t\) からそれぞれ単一始点最短路をすれば求まります。
s
|
o
|
o ＝ o ＝ o ＝ o ＝ o ＝ j
|
o
|
t
posted:
last update: