2688: 11_C : Breadth First Search

$INF\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$0$	正确数量	$1$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签	STL

Description

Breadth First Search

Write a program which reads an directed graph G=(V,E), and finds the shortest distance from vertex 1 to each vertex (the number of edges in the shortest path). Vertices are identified by IDs 1,2,...n.

Input

In the first line, an integer n denoting the number of vertices, is given. In the next n lines, adjacent lists of vertex u are given in the following format:

u k v1 v2 ... vk

u is ID of the vertex and k denotes its degree.vi are IDs of vertices adjacent to u.

Output

For each vertex u, print id and dd in a line. id is ID of vertex u and dd is the distance from vertex 1 to vertex u. If there are no path from vertex 1 to vertex u, print -1 as the shortest distance. Print in order of IDs.

Sample Input复制

Sample Output复制

提示

1≤ n≤ 100

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[ $3$ ms]	AOJ大管家	1163844	2025-01-14 19:38:45
内存最少[ $1448$ KB]	AOJ大管家	1163844	2025-01-14 19:38:45
第一AC	AOJ大管家	1163844	2025-01-14 19:38:45
第一挑战	AOJ大管家	1163844	2025-01-14 19:38:45

赛题来源/所属竞赛会津大学《挑战数据结构与算法》挑战数据结构与算法

竞赛编号	竞赛名称	竞赛时间	访问比赛

AOJ

祝同学们学习进步，编程快乐！

Please Login