第一篇题解没利用入度进行拓扑,而是通过前面的点慢慢把结果传递给输出层(乘法分配律),很新颖 (新颖的拓扑,古朴的bfs),但他进行了一个判断
if(c[h]<=0) continue;
就是如果当前点c<0就跳过。但想想前面说的,不是等所有u节点做完了v才入队,而是到v了就入队,后面再慢慢把没做的u节点的信息补充上,既然这样,为何c<0就跳过了呢,目前是<0但随着其他u节点的补充,c可能会大于0,跳过会错,hack如下
5 5
1 0
0 0
0 0
0 0
0 0
1 2 -10
1 3 4
3 4 6
4 2 7
2 5 1
应输出5 158
实际输出NULL
这个hack违反题意的话那就当我对这道题思考的痕迹了,如果成立那大家看看就好,不要撤了它,古老的题解,真的不想伤害它qwq