社区讨论

警示后人

MMoya_Rao啾？啾！

2025/09/17 15:53P1608路径统计参与者 18已保存回复 19

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复: 19 条
当前快照: 1 份
快照标识符: @mhj9xqgv
此快照首次捕获于: 2025/11/03 23:07
此快照最后确认于: 2025/11/04 06:02

注意这道题目是单向边，切记不可把：
CPP
```
p[u][v]=min(p[u][v],w);
```
写成：
CPP
```
p[u][v]=min(p[u][v],w),p[v][u]=min(p[v][u],w);
```
（其中 $p$ 代表邻接矩阵存图的那个数组）
Dijkstra 初始化的时候一定要记得 $cnt_1 = 0$ 。
当更新的时候，如果 $dis_u + p_{u,v} < dis_v$ ，一定要注意这个时候是 $cnt_v = cnt_u$ 而不是 $cnt_v = 1$ ！
即，不要把：
CPP
```
if(d+p[u][v]==dis[v])cnt[v]+=cnt[u];
else dis[v]=d+p[u][v],cnt[v]=cnt[u],q.push({v,dis[v]});
```
写成：
CPP
```
if(d+p[u][v]==dis[v])cnt[v]+=cnt[u];
else dis[v]=d+p[u][v],cnt[v]=1,q.push({v,dis[v]});
```
确实，按常规逻辑可能会错写，所以一定要注意了！

回复

共 19 条回复，欢迎继续交流。

正在加载回复...