よく考えると電車とバスのうち、どちらか一方は1手でnに辿り着ける。そのため、1手で辿りつけない乗り物のグラフ上で最短経路を求めればいい。nが小さいのでWarshall-Floydでも十分間に合う。

ダメ解法書いて見事に落ちた。これは失敗だ～。