处理负权边的方法十分巧妙,就像是势能一样
算法上文链接有详解,就不赘述了,这样就实现了dij也可以处理负边
是需要提前预处理一遍,建立超级源点用bellman-ford跑一遍就行
然后是第一个问题,总是TLE
然后发现自己dij的板子都打得有问题/kk
if(vis[tmp])continue;
一定要把放在前面判断,因为dij是按dis排序的,所以先遍历到一定dis更短
这个可以快不少
第二个问题是对于负权边的判断
我感觉这点还蛮重要的
对于松弛的计数并不是按照更新数来算的
而是对于是否更新且是否在队列中来算的
Old:
if (h[to] > h[node] + edge[i].value)
{
h[to] = h[node] + edge[i].value;
qcnt[to]++;
if (qcnt[to] > n)
return false;
if (!inqueue[to])
q.push(to), inqueue[to] = true;
}
New:
if (h[to] > h[node] + edge[i].value)
{
h[to] = h[node] + edge[i].value;
if (!inqueue[to])
{
q.push(to), inqueue[to] = true;
qcnt[to]++;
if (qcnt[to] > n)
return false;
}
}
这不是我的代码(我写的比较乱)
这其中蕴含的问题是一样的
hack数据
2 3
2 1 -3
2 1 -2
2 1 -1
由于重边的存在,所以只能用后者的写法
搞了一下午,菜死了/kk
标签:node,Johnson,P5905,全源,value,edge,inqueue,qcnt From: https://www.cnblogs.com/fleabag/p/16978070.html