为什么这样过不了Point11?(会错判成有负环)
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;
}
这样就可以:
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;
}
}
也就是说每更新一次不就应该松弛次数+1吗?而松弛不一定要入列(可能已经在队列里面)那为什么松弛次数的更新和判断不能放在外面?