BZOJ 3891 [Usaco2014 Dec]Piggy Back

发布于 2017-05-27  183 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3891

题意:一个无向图,边权均为 1,有两个人分别从点 1,2 出发,走 1 路程费用分别为 A,B,两人汇合后费用为 C,走到 n 最小费用


无聊刷水... 首先对 1,2,n 分别求一次单源最短路... 因为边权是 1 我就直接 bfs 了....

然后 O(n) 枚举汇合点即可.....

 


一个非常弱的准退役OIER