比赛场次 240
比赛名称 20130729
比赛状态 已结束比赛成绩
开始时间 2014-07-17 08:00:00
结束时间 2014-07-17 11:00:00
开放分组 全部用户
注释介绍
题目名称 捉迷藏
输入输出 hideseek.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar努力吧 AAAAAAAAAA 0.057 s 0.50 MiB 100
GravatarKZNS AAAAAAAAAA 0.058 s 0.49 MiB 100
Gravatar1azyReaper AAAAAAAAAA 0.061 s 0.69 MiB 100
Gravatar甘罗 AAAATTTEEE 3.457 s 95.56 MiB 40
GravatarFoolMike AAAATTTEEE 3.474 s 95.56 MiB 40
GravatarNBWang AAAWEEEEEE 0.452 s 0.17 MiB 30
Gravatar农场主 AWWWWWWWWW 0.009 s 8.02 MiB 10
Gravatarslyrabbit MMMMMMMMMM 0.000 s 0.00 MiB 0

捉迷藏

★☆   输入文件:hideseek.in   输出文件:hideseek.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

Bessie 正在玩捉迷藏游戏。(捉迷藏是这样玩的:在制定了奖罚规则后,玩家分为“捉”和“藏”两种,“藏”者有多个,在他们都藏起来后,由单独的一个“捉”者去找他们,这个游戏玩起来真是其乐无穷!)
Bessie 正在盘算她要藏到哪个牛棚里,一共有 $N(2\le N\le 20,000)$ 个牛棚,编号为 $1~N$。她知道“捉”者 FJ 会从 $1$ 号牛棚开始找。有 $M(1\le M\le 50,000)$ 条无向通路连接着所有的牛棚,其中通路 $i$ 的两个端点分别为 $A_i$ 和 $B_i$($1\le A_i\le N$;$1\le B_i\le N$;$A_i≠B_i$),任意两个牛棚之间都可互达。
Bessie 觉得藏到跟 $1$ 号牛棚距离最远的牛棚里会比较安全,(这里两个牛棚之间的距离是指从一个牛棚到另一个牛棚的最短路径),请帮 Bessie 算一下最佳躲藏位置。

【输入格式】

第 $1$ 行:两个空格隔开的整数 $N,M$;

第 $2~M+1$ 行:第 $i+1$ 行有两个整数 $A_i,B_i$,即第 $i$ 条路的两个端点;

【输出格式】

一行,三个空格隔开的整数,分别为:离 $1$ 号牛棚最远的牛棚编号(如果最远的有多个,输出编号最小的那个);最远的牛棚与 $1$ 号牛棚的最短路径;拥有此最短路径的牛棚个数。

【样例输入】

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

【样例输出】

4 2 3

【提示】

输入数据如图所示:

1--2--5

| /|

|/ |

3--4

|

6

4,5,6号牛棚距1号牛棚的最短路径均为2,选4号输出是因为它的编号最小。