全部评论
第一问并查集; 二三问其实可以当一问做,整个图所有边边权是1,所以第一次BFS到的路径就是最短路径。BFS的时候记录一下来源,倒着回去应该就可以了
十分典型的graph+bfs找最短路径~题解奉上 有一点疑惑的是,这三类关系面试官有做出什么其他的要求吗?比如要求指出每条边分别是什么关系之类的?如果有要求,还需要再定义一个类去记录边的信息
唉 冷静分析其实也不难 本来不想做 但是一想到这个题 确实是心里很难受 感觉过不去 还是决定直视这道题 克服一下自己吧 解法肯定不是最优的
邻接矩阵吧,用位表示关系。然后是bfs
看着像并查集的题目
建图+bfs
相关推荐
点赞 评论 收藏
分享