AtCoder AGC036D Negative Cycle (图论、DP)
题目链接https://atcoder.jp/contests/agc036/tasks/agc036_d题解这都是怎么想出来的啊。。目瞪口呆系列。。第一步转化至关重要: 一张图中不存在负环意味着什么？不存在负环就存在最短路，我们可以给每个点分配一个权值\(p_i\)(相当于从\(1\)号到该点的最短路，点从\(1\)开始标号)满足对于任何边\((i,j)\)有\(p_j\ge...
