简答题 偏难
#17721

图上移动 题目描述 小 A 有一张包含n 个结点与 m条边的无向图,结点以1,2,...,n 标号。小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前…

图上移动

题目描述

小 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 步之后可能位于的结点数量。


输入样例

4 4 3
1 2
1 3
2 3
3 4

输出样例

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。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n, m, k = map(int, input().split()) to = [[] for i in range(n + 2)] for i in range(m): x, y = map(int, input().split()) to[x].append(y) to[y].append(x) f = [[[False] * (n + 2) for _ in range(n + 2)] for __ in range(k + 2)] for i in range(1, n + 1): f[0][i][i] = True for t in range(1, k + 1): for x in range(1, n + 1): for y in range(1, n + 1): if f[t - 1][x][y]: for z in to[y]: f[t][x][z] = True for i in range(1, n + 1): Ans = [] for t in range(1, k + 1): ans = 0 for j in range(1, n + 1): ans += (f[t][i][j] == True) Ans.append(str(ans)) print(' '.join(Ans))</pre>
这道题暂未补解析。