\(\mathrm{dist}(x,y)\) を頂点 \(x\) と頂点 \(y\) の距離として定義します。 パス \(ST\) 上にある頂点の集合を \(P_{ST}\) と置くと、頂点 \(j\) に対する答えは \(\min_{i \in P_{ST}}(\mathrm{dist}(i,j)+1)\) となるため、 \(P_{ST}\) に含まれる頂点を始点とする多始点BFSを行う事でこの問題を \(\mathcal{O}(N)\) で解くことが出来ます。