原题目链接

此题显然为有向图判负权环板子题

没做过请先右转模板【负环】

此题关键点：

小明和小红的生活中，有N个关键的节点。有M个事件，记为一个三元组（Si，Ti，Wi），表示从节点Si有一个事件可以转移到Ti，事件的效果就是使他们之间的距离减少Wi。

所以建边时，要把权值变为相反数

然后以1为源点进行SPFA求负环，就AC了

……吗？

阅读全文