编程介的小学生 2018-12-24 16:59 采纳率: 0.4%
浏览 596
已采纳

一个类似于旅行商的问题,但是又有不同的地方,用C语言实现?

Problem Description
Jimmy lives in a huge kingdom which contains lots of beautiful cities. He also loves traveling very much, and even would like to visit each city in the country. Jaddy, his secretary, is now helping him to plan the routes, however, Jaddy suddenly find that is quite a tough task because it is possible for Jimmy to ask route’s information toward any city. What was worth? Jaddy has to response for queries about the distance information nearly between any pair of cities due to the undeterminable starting city which Jimmy is living in when he raises a query. Because of the large scale of the whole country, Jaddy feel hopeless to archive such an impossible job, however, in order to gratify his manager, Jaddy is now looking forward to your assistance.
There might be good news about Jaddy’s work: since Jimmy is very lazy and would not like to travel to a destination whose distance between the original city is larger than TWO. That means only one intermediate city among the route is acceptable (Apparently, all the connecting paths between any two cities, if exists, have the same length as ONE). But don’t be fooled: Jimmy also needs to know that how many alternative different routes are available so that he can have more options. In particular two routes were named as different if and only if there is at least one path in the two routes is distinguishable, moreover, if more than one paths exist between a particular pair of cities, they are considered as distinct.

Input
Input has multiple test cases. The first line of the input has a single integer T indication the number of test cases, then each test case following. For each test case, the first line contains two integers N and M indication the number of cities and paths in the country. Then M lines are following, each line contains a pair of integers A and B, separated by space, denoting an undirected path between city A and city B, all the cities are numbered from 1 to N. Then a new line contains a single integer Q, which means there are Q queries following. Each query contains a couple of integers A and B which means querying the distance and number of shortest routes between city A and B, each query occupy a single line separately.
All the test cases are separated by a single blank line.
You can assume that N, Q <= 100000, M <= 200000.

Output
For each test case, firstly output a single line contains the case number, then Q lines for the response to queries with the same order in the input. For each query, if there exists at least one routes with length no longer than TWO, then output two integer separated by a single space, the former is the distance (shortest) of routes and the later means how many different shortest routes Jimmy can choose; otherwise, output a single line contains “The pair of cities are not connected or too far away.” (quotes for clarifying). See the sample data carefully for further details.

Sample Input
2
5 7
1 2
2 3
3 4
4 5
2 5
2 4
1 2
4
1 4
1 2
5 3
5 4

2 0
2
1 1
1 2

Sample Output
Case #1:
2 2
1 2
2 2
1 1
Case #2:
0 1
The pair of cities are not connected or too far away.

展开全部

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-08-28 14:27
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥20 有人知道这是什么问题吗
  • ¥15 torch框架下的强化学习DQN训练奖励值浮动过低,希望指导如何调整
  • ¥35 西门子博图v16安装密钥提示CryptAcquireContext MS_DEF_PROV Error of containger opening
  • ¥15 mes系统扫码追溯功能
  • ¥40 selenium访问信用中国
  • ¥20 在搭建fabric网络过程中遇到“无法使用新的生命周期”的报错
  • ¥15 Python中关于代码运行报错的问题
  • ¥500 python 的API,有酬谢
  • ¥15 软件冲突问题,软件残留问题
  • ¥30 有没有人会写hLDA,有偿求写,我有一个文档,想通过hLDA得出这个文档的层次主题,有偿有偿!
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部