警示后人(该判NO PATH的地方却输出数字)
查看原帖
警示后人(该判NO PATH的地方却输出数字)
311152
Canace楼主2023/2/10 17:26

如果你是像我一样拓扑+Dij,并且判无解的时候用的是判断disdis是否等于INF,请注意:

老生常谈,最短路处理到负权路径,更新最小dis时

if(dis[v]>dis[u]+len[u][v]){
	dis[v]=dis[u]+len[u][v]
}

要注意判断dis[u]dis[u]是否是INF,不然在len[u][v]len[u][v]为负值时dis[v]dis[v]会被更新成INF减去一个数,这样就无法判断dis[v]dis[v]是否无解

2023/2/10 17:26
加载中...