AI题库 · GESP-C++七级题库
题目分享 #20429
图上移动
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一张包含 个n 结点与 m 条边的无向图,结点以 1、2、……、n 标号。
小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。
对于每个结点 i(1<=i<=n),小 A 想知道从结点 i 出发恰好移动步1、2、……、k 之后,小 A 可能位于哪些结点。
由于满足条件的结点可能有很多,你只需要求出这些结点的数量。
【输入描述】
第一行,三个正整数 n、m、k,分别表示无向图的结点数与边数,最多移动的步数。
接下来 m 行,每行两个正整数 ui、vi,表示图中的一条连接结点 ui 与 vi 的无向边。
【输出描述】
共 n 行,第 i 行(1<=i<=n )包含 k 个整数,第 j 个整数( 1<=j<=k)表示从结点 i 出发恰好移动 j 步之后可能位于的结点数量。
【样例输入1】
4 4 3
1 2
1 3
2 3
3 4【样例输出1】
2 4 4
2 4 4
3 3 4
1 3 3【数据范围】
对于 20% 的测试点,保证 k=1。
对于另外 20% 的测试点,保证 1<=n<=50,1<=m<=50 。
对于所有测试点,保证 1<=n<=500,1<=m<=500 ,1<=k<=20 ,1<=ui、vi<=n 。
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。