网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P3547
2024-10-23
P3547 [POI2013] CEN-Price List
很不错的图论题。考虑对\(a,2a,b\)大小进行讨论。\(2a\leb\),这种情况是简单的,根本不会走\(b\)边,直接bfs即可,此时答案为\(d*a\)。\(a\leb<2a\),这种情况下能走两条\(a\)边就会用\(b\)边替换掉,同时不用担心三元环的情况(因为三元环会出现三个点最短路都是\(1