GESP认证C++编程真题解析 | P11964 [GESP202503 七级] 图上移动

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：P11964 [GESP202503 七级] 图上移动 - 洛谷 (luogu.com.cn)

【题目描述】

小 A 有一张包含n nn个结点与m mm条边的无向图，结点以1 , 2 , … , n 1,2,…,n1,2,…,n标号。小 A 会从图上选择一个结点作为起点，每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点i ( 1 ≤ i ≤ n ) i (1≤i≤n)i(1≤i≤n)，小 A 想知道从结点i ii出发恰好移动1 , 2 , … , k 1,2,…,k1,2,…,k步之后，小 A 可能会位于哪些结点。由于满足条件的结点可能有很多，你只需要求出这些结点的数量。

【输入】

第一行，三个正整数n , m , k n,m,kn,m,k，分别表示无向图的结点数与边数，最多移动的步数。

接下来m mm行，每行两个正整数u i , v i u_i,v_iui​,vi​，表示图中的一条连接结点u i u_iui​与v i v_ivi​的无向边。

【输出】

共n nn行，第i ii行( 1 ≤ i ≤ n ) (1≤i≤n)(1≤i≤n)包含k kk个整数，第j jj个整数( 1 ≤ j ≤ k ) (1≤j≤k)(1≤j≤k)表示从结点i ii出发恰好移动j jj步之后可能位置的结点数量。

【输入样例】

4 4 3 1 2 1 3 2 3 3 4

【输出样例】

2 4 4 2 4 4 3 3 4 1 3 3

【算法标签】

《洛谷 P11964 图上移动》 #动态规划DP# #GESP# #2025#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=505,K=25;// 定义最大节点数N和最大步数Kintn,m,k;// n: 节点数，m: 边数，k: 最大步数intvis[N][K];// 记录节点u在step步内是否能被访问到inth[N],e[N*2],ne[N*2],idx;// 邻接表存储图// 添加边到邻接表voidadd(inta,intb){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}// 深度优先搜索voiddfs(intu,intstep){if(vis[u][step])return;// 如果当前状态已访问，直接返回vis[u][step]=1;// 标记当前状态为已访问if(step==k)return;// 如果达到最大步数，停止递归// 遍历所有邻居节点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];dfs(j,step+1);// 递归访问邻居节点，步数加1}}intmain(){cin>>n>>m>>k;// 输入节点数、边数和最大步数memset(h,-1,sizeofh);// 初始化邻接表// 构建图的邻接表for(inti=1;i<=m;i++){inta,b;cin>>a>>b;add(a,b),add(b,a);// 无向图，添加双向边}// 对每个节点进行DFS，统计在1到k步内能到达的节点数for(inti=1;i<=n;i++){memset(vis,0,sizeofvis);// 初始化访问数组dfs(i,0);// 从节点i开始DFS，初始步数为0// 输出从节点i出发，在1到k步内能到达的节点数for(intj=1;j<=k;j++){intres=0;for(intkk=1;kk<=n;kk++){res+=vis[kk][j];// 统计在j步内能到达的节点数}cout<<res<<" ";}cout<<endl;}return0;}

【运行结果】

4 4 3 1 2 1 3 2 3 3 4 2 4 4 2 4 4 3 3 4 1 3 3