AOJ0304がコーナーケースを入れ損ねてるっぽい話

競プロとLPまわりの記事 :
github.com
をupdateしたくなったので色々整理しているとこういう話になっているっぽいことを確認しました。

これらに

5 4
1<=2-2
4>=3-2
5>=4-1
5>=3+4

の入力を与えるとき、前者はinf,後者は-1が出力されます。

入力に対する解説をすると、
始点1から到達不可能な点であっても負閉路が検出されるときは
validな配置が存在しないため-1になるべきということです。

それぞれのBellman-Ford法を眺めてみると、
前者の実装では始点以外INFで初期化をしてINFがあれば更新をしないのに対し、
後者の実装では始点以外INFで初期化をしたもののINFがあっても更新をしています。
この差が反映されて出力の差異が発生しています。

これらのコードが両方ACされているため、
ジャッジケースにはこういうコーナーケースは入っていないのだと思われます。
今後、類題が出題される、もしくは類題を出題するときには気をつけたいところです。

とこはるのまとめ