2020/05/26

UNDERTALEおもしろい．

研究

文献 2h

サボりすぎた．明日はもう少し．

競プロ

AtCoder : 4AC

E - Coins Respawn

解説AC : 80分

難問でした．というのも最初はベルマンフォードのなかで，最終コストを各辺に載せる発想が出てこなくて詰んでました．それがわかってからも，スタートからゴールまでに負閉路があるかどうかを検出する発想が出てこなかった．結局，負閉路検出パートで更新があった際にその頂点の最短距離を-infにして，最終的なゴールである頂点 $N$ の最短距離が-infならアウトにする，という手法をとりました．