欢迎光临散文网 会员登陆 & 注册

【洛谷题解/C++】P8881 懂事时理解原神

2023-07-13 12:43 作者:jfmd_6p  | 我要投稿

胡桃敲可爱的~

分析、实现

先贴上 dijkstra 求最短路的代码:

与题中的 dfs 对比,很容易发现在 dijkstra 算法中,每当一个结点 v 被进行计算时,它会比较所有的前驱结点,最终留下最优值。

但在 dfs 算法中,一个结点最多只会被计算一次。不难发现,当一个结点有且仅有一个前驱时,dfs 算法才能正确计算最短路。

而此时图实际上是一棵无根树,这个 dfs 算法实际上是用来计算树上结点深度的正解。

所以当且仅当结点 1 所在连通块是一棵树时,才能正确进行最短路计算。否则,一旦结点 1 所在连通块中出现环,环上部分节点计算必然出错。

综上所述,只需要对结点 1 所在连通块检查是否存在环即可。

(其实还有一种简单粗暴的办法,用 dfs 和 dijkstra 各运行一遍,比较答案。)

Code

胡桃敲可爱的~

【洛谷题解/C++】P8881 懂事时理解原神的评论 (共 条)

分享到微博请遵守国家法律