- 题目提供者 FarmerJohn2
- 评测方式 云端评测
- 标签 SPFA 最短路 USACO 2009
- 难度 普及/提高-
- 时空限制 1000ms / 128MB
Bessie is playing hide and seek (a game in which a number of players hide and a single player (the seeker) attempts to find them after which various penalties and rewards are assessed; much fun usually ensues).
She is trying to figure out in which of N (2 <= N <= 20,000) barns conveniently numbered 1..N she should hide. She knows that FJ (the seeker) starts out in barn 1. All the barns are connected by M (1 <= M <= 50,000) bidirectional paths with endpoints A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i); it is possible to reach any barn from any other through the paths.
Bessie decides that it will be safest to hide in the barn that has the greatest distance from barn 1 (the distance between two barns is the smallest number of paths that one must traverse to get from one to the other). Help Bessie figure out the best barn in which to hide.
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains the endpoints for path i: A_i and B_i
第2-M+1行：每行两个整数，表示端点A_i 和 B_i 间有一条无向边。输出格式：
* Line 1: On a single line, print three space-separated integers: the index of the barn farthest from barn 1 (if there are multiple such barns, print the smallest such index), the smallest number of paths needed to reach this barn from barn 1, and the number of barns with this number of paths.
The farm layout is as follows:
Barns 4, 5, and 6 are all a distance of 2 from barn 1. We choose barn 4 because it has the smallest index.
感谢 wjcwinmt 的贡献翻译