北邮复试_2019_树的某两个节点的最短路径（广度优先算法）
4 浏览量
2021-01-06
19:53:44
上传
评论
收藏 27KB PDF 举报
北邮复试北邮复试_2019_树的某两个节点的最短路径（广度优先算法）树的某两个节点的最短路径（广度优先算法）
题目描述题目描述
题目描述
对二叉树，计算任意两个结点的最短路径长度。
输入
第一行输入测试数据组数T
第二行输入n,m 。n代表结点的个数，m代表要查询的数据组数
接下来n行，每行输入两个数，代表1~n结点的孩子结点，如果没有孩子结点则输入-1.根节点为1.
接下来m行，每行输入两个数，代表要查询的两个结点
输出
每组测试数据输出m行，代表查询的两个结点之间的最短路径长度
测试样例
输入
1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1
输出
2
4
2
4
void short_tree_path() //最短路径（广度优先遍历）
{
int n;
cin >> n;
for (int i = 0; i > vernums;
cin >> testnums;
vector visit(vernums, false);
vector<vector> edge(vernums, vector(vernums, -1));
int left, right;
for (int i = 0; i > left;
cin >> right;
if (left != -1)
{
edge[i][left - 1] = 1;
edge[left-1][i] = 1;
}
if (right != -1)
{
edge[i][right - 1] = 1;
edge[right - 1][i] = 1;
}
}
vector<vector> test(testnums,vector(2,0));
for (int i = 0; i > left;
cin >> right;
test[i][0] = left - 1;
test[i][1] = right - 1;
}
vectorres(testnums,0);
for (int i = 0; i < testnums; i++)
{
visit = vector(vernums, false);
vector pathlong(vernums, 0);
int start = test[i][0];
int end = test[i][1];
visit[start] = true;
queue m_queue;
m_queue.push(start);
资源评论
weixin_38723691
- 粉丝: 3
- 资源: 941
最新资源
- Integrated-Energy-Systems-with-CAES-(注释完全，可直接运行)
- PDF为英语文本绘制热区（DEMO）
- 4.22.cpp
- 基于Transformer和Bert的close domain抽取式问答系统构建的智能聊天机器人项目源代码
- 基于扩展(EKF)和无迹卡尔曼滤波(UKF)的电力系统动态状态估计(注释完全，可直接运行)(文档加Matlab源码)
- 2023各大软件技术峰会演进资料汇总（PPT），资料难得
- 基于混沌集成决策树的电能质量复合扰动识别(注释完全，可直接运行)(文档加Matlab源码)
- 航空公司如何成功实现数字化转型英文版.rar
- RTL8309N-8口交换机评估板Cadence设计硬件(原理图+PCB)及PDF原理图+RTL8309N技术规格书
- 基于JAVA的打飞机游戏设计（程序）.zip
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
