基本的な方針は公式解説の解法 1 と同じです。

公式解説同様に、\(i\) から \(j\) に辺がある ⟺ 薬 \(i\) を使った後他の薬を使わずに薬 \(j\) の位置にたどり着ける となる \(N\) 頂点の有向グラフを作ったあとのことを考えます。また、同様にスタート地点とゴール地点用の頂点を用意し、辺を張ります。

計算量 \(O(HWN + N^3)\) で、ワーシャルフロイド法を使うことができます。

方法 1

普通の最短路問題におけるワーシャルフロイド法に帰着させます。

さきほど構築したグラフについて、\(i\) から \(j\) に辺があるなら \(i\) から \(j\) への距離は \(0\) とします。そうでないなら、正の適当な数字を距離とすればよいです。その後、ワーシャルフロイド法を適用すると、スタートからゴールまでの距離が \(0\) ならたどり着けることになります。

実装例 (C++)

方法 2

ワーシャルフロイド法における　「\(i\) から \(j\) への距離を、\(i\) から \(k\) への距離と \(k\) から \(j\) への距離の和との 小さい方で置き換える」という処理の部分を改造します。

薬を好きに使って良いとき、\(i\) から \(k\) にたどり着けて、\(k\) から \(j\) にたどり着けるならば、 \(i\) から \(j\) にたどり着けます。

\(f_{x, y}\) を、「\(x\) から \(y\) にたどり着けるなら \(1\) 、そうでないなら \(0\)」として、「 \(f_{i, j}\) を \(f_{i, k} ~\text{AND}~ f_{k, j}\) との \(\text{OR}\) で置き換える」とすればよいです。

実装例 (C++)