\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC061D 解法 0: コストを -1 倍することで,min cost の問題に帰着できる. ただし,負のコストがあるため,Dijikstra は使えない. Bellman-Ford に近い解法なら,負のサイクルも検出できて \(O(NM)\) . 負のサイクルが存在しない場合は,最大で path の長さが \(N-1\). 負のサイクルが存在するなら,最大で cycle の長さが \(N\). まず,暫定的な min dist を求める. これは edge の更新を \(N-1\) 回繰り返せば十分. 暫…