最少转车次数

提交数: 383, 通过率: 50.91%, 平均分: 61.68

题目描述:

小华从某起点到某目的地需要经过若干次公交转车( 乘车不存在绕圈现象,但不保证可以到达目的地 ),显然坐车的方案可能不唯一。如下图所示,从起点A到目的地H可以选择公交线路“A -> D -> E -> F -> H”,也可以选择公交线路“A -> D -> G -> H”。前者需要在“D”、“E”、 “F”三个公交车站下车后转车3次,而后者只需要在“D”和“G”两个公交车站下车后转车2次,且是所有乘坐公交车方案里转车次数最少的一种方案。

1657372375962988980.png

现给出某公交车坐车方案图,求从起点A到目的地的最少转车方案。

输入格式:

第一行三个整数 n, m,n表示图中的顶点数,m表示有向图的边数;

接下来共m行,每行两个整数(i,j),为图G中的一条有向边;

最后一行一个字母,表示目的地。

输出格式:

一个数,表示最少的转车次数。

数据范围:

图中顶点数小于26个,边数小于50条。

样例输入:

8 10
A B
A D
B C
C F
D E
E C
E F
D G
F H
G H
H

样例输出:

2

提示:

#作业本,P31,第6题

n, m  = map(int, input().split() )

a=[ [ 0 for i in range( n ) ] for j in range( n ) ]

for i in range( m ):    #建图
    x,   y = input().split()
    _______________________   #(1)

q = [0] * n
f = [False] * n
b = { }   #存放每个顶点的步数
head =0
tail = 0
q[tail] =0 ;   ____________    #(2)
f[0] = True
b[0] = 0
to = ord( input()[0] ) - 65 
flag = False
while head<tail and flag == False :
    _______________________       #(3)
    head += 1
    for j in range( n ):
        if j != c:
            if j != to and a[c][j] == 1 and f[j] == False:
                q[ tail ] = j; tail += 1
                f[j] = True
                b[j] = b[c] +1
            elif j == to and a[c][j] == 1:
                ________________   #(4)
                ________________   #(5)
                break
if flag == False :
    print( "NO PATH!" )
    
#A对应0,B对应1,H对应7
#a[0][1] = 1  A -> B
#a[0][3] = 1  A -> D
#a[1][2] = 1  B -> C
#a[2][5] = 1  C -> F
#a[3][4] = 1  D -> E
#a[4][2] = 1  E -> C
#a[4][5] = 1  E -> F
#a[3][6] = 1  D -> G
#a[5][7] = 1  F -> H
#a[6][7] = 1  G -> H
时间限制: 1000ms
空间限制: 256MB

来源: 省编作业本3-P31