這題建圖沒什麼特別
x個條件:Sb-Sa<=c
y個條件:Sa-Sb<=-c
題目問的是,1和n之間的關系。
有負環的話,整個就不可能成立,輸出-1
如果圖是連通的(1到n是連通的),就輸出d[n]
不連通就是題目中說-2的情況。
原來我們建圖一般添加一個附加結點,或者開始就把所有點入隊,就是考慮到不連通的問題,所以添加一個沒有意義的條件。
#include
#include
#include
#include
#include
#include
#include
#include
#include