この問題は、グラフの単一始点最短経路問題とみなすことができます。

例えば入出力例1であれば、下図のグラフにおける、頂点”高橋”から各頂点への最短経路を求める問題となります。したがって、ダイクストラ法を用いて \(O(N\log N)\) で解くことができました。