众所周知,差分约束抽象出的最短路模型没用规定的源点,使用加了一个超级源点:
for(int i = 1;i <= n;i++) add(S,i,0);
这个式子相当于disi−disS≤0dis_i - dis_S \leq 0disi−disS≤0 的限制,由于 disS=0dis_S = 0disS=0,所以有了 disi≤0dis_i \leq 0disi≤0
那么对于有 disS≥0dis_S \geq 0disS≥0 限制的题目该如何改进使得最短路模型仍然有用