题目传送门:F - Shortest Good Path (atcoder.jp) 啊shit,这题没做出来啊。这个dp状态属实想不到,之前写了好几次dfs都T了,看了题解才明白,用bfs好多了。 dfs无法保证第一个拓展到的点是长度最短的,但是bfs可以,然后下一次就不会拓展已经拓展了的点。于是bfs的复杂度比dfs低了很多。 题目大意 有一个N个点,M条无向边,现在有2^N条线路,分别是0 ~ […]
题目传送门:F - Shortest Good Path (atcoder.jp) 啊shit,这题没做出来啊。这个dp状态属实想不到,之前写了好几次dfs都T了,看了题解才明白,用bfs好多了。 dfs无法保证第一个拓展到的点是长度最短的,但是bfs可以,然后下一次就不会拓展已经拓展了的点。于是bfs的复杂度比dfs低了很多。 题目大意 有一个N个点,M条无向边,现在有2^N条线路,分别是0 ~ […]
Eriktse
18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。
COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.
Theme Kratos | Hosted In TENCENT CLOUD