适用范围

单源最短路问题(允许存在负边)

思路

初始化d[i]数组为INF,d[i]表示起点到该点的最短距离,INF表示起点无法到达该点,然后用if(d[j]!=INF) dp[i]=min{dp[j]+(从j到i的边的权值)|e=(i,j)}

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄