-->
当前位置:首页 > 题库

PROGRAMMING:Travel around the world

Luz5年前 (2021-05-10)题库365
It's romantic to travel around the world, but it's not necessary to plan travel routes... There are thousands of routes, railways and buses all over the world, which are dazzling. So the travel society chooses some transportation companies to form an alliance, each company provides a route, and then helps customers plan the travel route supported by the enterprises in the alliance. This problem requires you to help travel agencies to achieve an automatic route planning process, so that for any given starting point and destination, you can find the most smooth route. The so-called "smoothest" means, first of all, the least stops on the way; If there are the same number of stops, take the route that needs the least number of transfer lines.
###Input format:
Enter a positive integer $$n $$($$Le 100 $$) in the first line, that is, the number of alliance companies. Next, there is line $$n $, and line $$I $($$I = 1, cdots, n $) describes the lines provided by company $$I $. The format is:
$$M$$ S[1] S[2] $$\cdots$$ S[$$M$$]
Where $$M $$($$Le 100 $$) is the number of stops, and s [$$I $$] ($$I = 1, cdots, M $$) is the number of stops (composed of 4 digits 0-9). It is assumed that each line is a simple two-way link, and the input guarantee is given according to the correct stop sequence - that is, there is no other stop station between any pair of adjacent s [$$I $$] and s [$$I + 1 $$] ($$I = 1, cdots, M-1 $$). We call the line between adjacent stations as an operation section, and each operation section is contracted to only one company. Loop line is possible, but it will not return from the starting point to the starting point without stopping any intermediate station. Of course, lines of different companies may intersect at some stations, which are customer transfer points. We assume that no more than 5 lines of different companies are involved in any transfer point.
After describing the alliance route, the topic will give a positive integer $$k $$($$Le 10 $$), followed by $$k $$lines. Each line gives a customer's demand, that is, the number of the origin and the number of the destination, separated by a space.
###Output format:
Deal with the needs of every customer. If there is no ready-made line to make it reach the destination, output "sorry, no line is available."; If the destination is reachable, first output the number of stops of the smoothest route in a row (excluding the origin and destination), and then give the travel route in the following format:
```
Go by the line of company #X1 from S1 to S2.
Go by the line of company #X2 from S2 to S3.
......
```
Where 'Xi' is the number of the line contractor and 'Si' is the number of the transit station. But it must only output the origin, transfer point and destination, not the middle stop. There is only one way to ensure that the requirements are met.
###Input example:
```in
four
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
four
3011 3013
6666 2001
2004 3001
2222 6666
```
###Output example:
```out
two
Go by the line of company #3 from 3011 to 3013.
ten
Go by the line of company #4 from 6666 to 1306.
Go by the line of company #3 from 1306 to 2302.
Go by the line of company #2 from 2302 to 2001.
six
Go by the line of company #2 from 2004 to 1204.
Go by the line of company #1 from 1204 to 1306.
Go by the line of company #3 from 1306 to 3001.
Sorry, no line is available.
```






answer:If there is no answer, please comment