yukicoder 1344 Typical Shortest Path Sum
問題を見ると最短経路問題を解けばよいということがわかる. ここでは全頂点対最短経路問題を$ O(N^3)で解くことができるWarshall-Floyd法が最も適している. しかし愚直に実装しても通らない.
実はたどりつけない頂点については最短経路の値が$ INFかどうかで判定するのではなく, $ INF / 2以上かで判定することが必要となってくる. これは負の辺が含まれ, $ INFより小さくなる可能性があるからである.
Warshall-Floyd法の実装では常に気を付けるべきだろう.
実装例: https://yukicoder.me/submissions/605837