anyiak
立身须正,为人当明
安逸的网络日志
最短路计数问题

定义cnt[i]表示源点到i点的最短路条数。

通过v点松弛源点r到u的距离时,若成功松弛(d[v]+val[i]<d[u]),r→v的最短路条数取代了r→u的最短路条数(cnt[u]=cnt[v];),因为最短路不是同一个长度了,所以之前记录的作废。

若新路径和目前最短路长度一样(d[v]+val[i]==d[u])则最短路的数量增加(cnt[u]+=cnt[v];

当然,初始时cnt[r]=1

发表评论

textsms
account_circle
email

安逸的网络日志

最短路计数问题
定义cnt[i]表示源点到i点的最短路条数。 通过v点松弛源点r到u的距离时,若成功松弛(d[v]+val[i]<d[u]),r→v的最短路条数取代了r→u的最短路条数(cnt[u]=cnt[v];),因为最短路不…
扫描二维码继续阅读
2020-12-25