AOJ 2913 - Problem J. Prime Routing

問題リンク

解説

まず2が可能かどうかを確認しましょう。可能なら2です。

以下、2では間は移動できないものとします。

2より大きい素数はすべて奇数であることに注意しましょう。

ここで、間に奇数で行く経路がなければ、-1です。

そうでなければ、を奇数でいける最短経路を考え、それに最も近い素数を見つければいいです。(の辺のどこかを往復していれば、その素数の値になります)

提出コード

onlinejudge.u-aizu.ac.jp