线路图的匹配算法问题,逻辑的运算,怎么利用C语言实现这个逻辑

Problem Description
Many cities provide a comprehensive public transport system, often integrating bus routes, suburban commuter train services and underground railways. Routes on such systems can be categorised according to the stations or stops along them. We conventionally think of them as forming lines (where the vehicle shuttles from one end of the route to the other and returns), loops (where the two ends of the ``branch'' are the same and vehicles circle the system in both directions) and connections, where each end of the route connects with another route. Obviously all of these can be thought of as very similar, and can connect with each other at various points along their routes. Note that vehicles can travel in both directions along all routes, and that it is only possible to change between routes at connecting stations.

To simplify matters, each route is given a designation letter from the set A' toZ', and each station along a route will be designated by another letter from the set a' toz'. Connecting stations will have more than one designation. Thus an example could be:

A common problem in such systems is finding a route between two stations. Once this has been done we wish to find the best'' route, wherebest'' means ``shortest time''.

Write a program that will read in details of such a system and then will find the fastest routes between given pairs of stations. You can assume that the trip between stations always takes 1 unit of time and that changing between routes at a connecting station takes 3 units of time.

Input
Input will consist of two parts. The first will consist of a description of a system, the second will consist of pairs of stations. The description will start with a number between 1 and 26 indicating how many routes there are in the system. This will be followed by that many lines, each describing a single route. Each line will start with the route identifier followed by a :' followed by the stations along that route, in order. Connections will be indicated by an=' sign followed by the complete alternative designation. All connections will be identified at least once, and if there are more than two lines meeting at a connection, some or of all the alternative designations may be identified together. That is, there may be sequences such as `...hc=Bg=Cc=Abd...'. If the route forms a loop then the last station will be the same as the first. This is the only situation in which station letters will be repeated. The next portion of the input file will consist of a sequence of lines each containing two stations written contiguously. The file will be terminated by a line consisting of a single #.

Output
Output will consist of a series of lines, one for each pair of stations in the input. Each line will consist of the time for the fastest route joining the two stations, right justified in a field of width 3, followed by a colon and a space and the sequence of stations representing the shortest journey. Follow the example shown below. Note that there will always be only one fastest route for any given pair of stations and that the route must start and finish at the named stations (not at any synonyms thereof), hence the time for the route must include the time for any inter-station transfers.

The example input below refers to the diagram given above.

Sample Input
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#

Sample Output
5: Agfdjba
9: Abaz=Bdefgh
10: Bhg=Cbac=Dcf

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

5
关于计算机视觉模板匹配问题的算法解决思路
0
用c#做出基于KMP匹配算法的文学研究助手系统
0
一个姓名的匹配算法的实现过程的分解,数据结构C语言解决这个问题的思路方式
1
数据结构上的一个线性表的冲突的解决,是不是用哈希算法怎么采用C语言的实现方式
0
一个和纸牌策略有关的算法算法问题,怎么利用C语言解决
0
请教一个有关随机数生成算法方面的算法问题,利用C语言算法的实现的过程方式
0
一个和概率生成有关的算法问题,请教如何利用C语言的综合技术编写?
0
全局搜索和局部搜索最优的一个相关的算法问题,如何利用C语言的编程的方式
0
一个立体的分割蛋糕的算法问题,请问如何利用C语言的形式解决
0
请问这个选择优化的算法问题输出序列如何是利用C语言的技术?
0
集合的匹配的一个算法问题的解释?如何利用C语言实现的
0
数字匹配判断是否能够开锁的一个问题,加锁算法,利用C语言解决的办法
0
碎片的匹配的问题,Map的算法,运用C语言的办法
0
子树的查询的一个算法的问题,如何利用C语言的方式去计算
0
几何对称和最小剪裁次数的算法问题,如何利用C语言计算的
0
字符串子串寻找不同的算法问题,如何利用C语言编程解决的呢
0
数据结构的括号的嵌套的判断和匹配的算法,利用C语言编程实现
0
列竖式计算的一个代换问题的算法难题,采用C语言如何运算的
0
字母的排列构成的单词的算法的问题,是如何利用C语言的办法实现呢
0
字符串带格式的格式化的问题算法,请教如何利用C语言的方式实现