题目
一个游乐园,有n个项目。初始有一些积分,可以在任意一个项目开始游玩。当完成一个项目时,会存在若干条道路通往其他项目。
但是游乐园里的道路有一些限制,对于第i条道路,完成项目xi;后可以单向通往项目yi,同时需要至少ai的积分才能选择走这条道路(并不会消耗积分),并且经过后会得到bi积分。
如果想游乐园里无限地玩下去,那么初始分数最少是多少?如果无论如何都无法在游乐园中无限地玩下去,则输出-1。
输入项目书n和道路数m。接下来输入m行,每行分别是x y a b(变量意义看题描述)
n,m<=2000, a,b<=1e9
input:
5 5
4 2 4 0
3 2 3 0
2 4 1 1
4 3 3 1
5 3 0 2
output:
1
解释:
选择5为起点,初始最少1个积分。
从5到3,需要0积分,得到2分,目前共3积分。
从3到2,需要3积分,得到0分,目前共3积分。
从2到4,需要1积分,得到1积分,目前共4积分:
从4到3,需要3积分,得到1积分,目前共5积分。
随后在3->2->4->3中便可以无限地游玩下去。
有无大佬知道怎么做吗?
根据点权和边权建图,然后跑正环判定和最长路,乱搞估计就A了
感谢 我试试