exercise_smile
exercise_smile
采纳率100%
2021-02-27 13:30

PTA 7-3 幸福小镇的故事! (最短路径直接用floyd会超时怎么办?)

已采纳

7-3 幸福小镇的故事!(简单) (25 分)

在一个很远很远的地方,有一个幸福小镇!

幸福小镇的治安很不好,所以生活在镇上很不幸福!

新来的保安队队长小Z决心改变这一切,第一步要解决的是任何两个小镇之间的距离问题!

我们需要解决这个问题的简化版本:

幸福小镇可以划分为N个小小镇,从1到N编号!这些小小镇由N-1条道路连通,我们把每条道路的长度简化为1!只要在每个小小镇增派人手,就可以让小镇的治安情况变得越来越好!(题目保证两个小镇之间的道路只有一条!)

每次小Z会询问你两个小小镇的编号,请你计算出这两个小镇之间的最短路径长度!

输入格式:

第一行包含一个正整数(N<=1000),表示小小镇的个数!

接下来N-1行,每行包含两个1到N之间的整数,表示这两个编号的小小镇之间有一条路!

接下来一行包含一个整数q(q<=100),表示询问数!

接下来q行,每行包含两个小小镇的编号,请在一行中输出这两个小小镇的最短路径长度!

输出格式:

输出答案即可!

输入样例:

在这里给出一组输入。例如:

10
1 2
2 3
1 4
4 5
4 6
3 7
3 8
1 9
9 10
5
3 8
9 3
1 1
1 7
1 9

输出样例:

在这里给出相应的输出。例如:

1
3
0
3
1
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • QSTARTmachine Corleo 2月前

    直接bfs就行了,毕竟询问次数较少

    点赞 1 评论 复制链接分享
  • exercise_smile exercise_smile 2月前

    来个大神指点一下吧

    点赞 评论 复制链接分享