【洛谷题解/C++】P8881 懂事时理解原神
胡桃敲可爱的~
分析、实现
先贴上 dijkstra 求最短路的代码:
与题中的 dfs 对比,很容易发现在 dijkstra 算法中,每当一个结点 被进行计算时,它会比较所有的前驱结点,最终留下最优值。
但在 dfs 算法中,一个结点最多只会被计算一次。不难发现,当一个结点有且仅有一个前驱时,dfs 算法才能正确计算最短路。
而此时图实际上是一棵无根树,这个 dfs 算法实际上是用来计算树上结点深度的正解。
所以当且仅当结点 所在连通块是一棵树时,才能正确进行最短路计算。否则,一旦结点
所在连通块中出现环,环上部分节点计算必然出错。
综上所述,只需要对结点 所在连通块检查是否存在环即可。
(其实还有一种简单粗暴的办法,用 dfs 和 dijkstra 各运行一遍,比较答案。)
Code
胡桃敲可爱的~