Come Back Quickly

頂点を (町の番号, 辺を 1 本以上使ったか) としたグラフで Dijkstra

元のグラフで a → b に辺があったとき、次のように辺を引く

(a, 0 本) → (b, 1 本以上)

(a, 1 本以上) → (b, 1 本以上)

答えは、スタート頂点を s として (s, 0 本) から (s, 1 本以上) までの最短距離