信息学一本通,图论2407: 信息学奥赛一本通T1498-Roadblocks题解

凸凸曼凸凸 算法基础篇 57 0
挑战自我,勇攀编程高峰!全网最全C++题库,助您成为编程达人。
贝茜把家搬到了一个小农场,但她常常回到 FJ 的农场去拜访她的朋友,贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路,贝茜选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且一条路可以重复走多次,当然第二短路的长度必须严格大于最短路的长度,但它的长度必须不大于所有除最短路外的路径的长度。

原题来自:USACO 2006 Nov. Gold 贝茜把家搬到了一个小农场,但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有 R(1≤R≤105) 条双向道路,每条路都连接了所有的 N(1≤N≤5000) 个农场中的某两个。贝茜居住在农场 1,她的朋友们居住在农场 N(即贝茜每次旅行的目的地)。 贝茜选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且一条路可以重复走多次。当然第二短路的长度必须严格大于最短路(可能有多条)的长度,但它的长度必须不大于所有除最短路外的路径的长度。

信息学一本通,图论2407: 信息学奥赛一本通T1498-Roadblocks题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
全网最全C++题库,助您挑战自我,突破极限,成为编程领域的佼佼者!

标签: 信息学一本通 图论2407: 信息学奥赛一本通T1498-Roadblocks题解