Python-程式代碼問題

Question

求改題程式碼

小白要到納美克星的城市旅遊，某些城市之間有傳輸通道可以走。小白聽說B城市特別好玩，因此到目的地之前一定要經過B城市，但小白又不想走太多路，因此需要同學幫小白找出一條能從A城市到C城市，並且中途一定會經過B城市的最短路徑。

輸入說明
第一行N, X, Y,Z，星球中有N個傳輸通道，X,Y,Z分別代表起始點X城市、特別好玩的城市Y、終點Z城市。
之後N行，每一行X Y，代表X城市與Y城市之間有傳輸通道可以走。

輸出說明
X是否中途可以經過Y城市並且最終可以抵達Z城市。
如果可以則輸出：
X到Y城市過程中走過的最少通道個數以及最短路徑

若不行則輸出 No way!

注意:
1.因會有資料量較大的測試資料，請嘗試使用BFS(廣度優先搜尋 / Breadth-First Search)+Queue完成。

2.使用窮舉法或遞迴可能導致timeout。

範例輸入1:
6 1 3 4
1 2
1 3
2 4
2 5
3 5
5 4

範例輸出1:
3
1-3-5-4

範例輸入2:
13 1 4 10
1 4
1 5
2 4
3 5
3 4
3 2
4 3
5 2
6 3
7 10
8 7
9 7
10 8

範例輸出2:
No way!

範例輸入3:
12 1 4 9
1 2
1 3
2 3
2 4
2 5
3 9
4 6
6 7
6 8
7 9
4 5
5 9
範例輸出3:
4
1-2-4-5-9

範例輸入4:
134 1 32 57
1 32
1 4
1 12
2 7
3 6
3 23
3 67
3 68
4 45
4 11
5 70
5 66
6 44
6 28
7 3
7 25
7 89
8 4
8 83
8 12
8 40
9 21
9 41
9 4
9 2
10 99
10 69
11 49
11 10
11 96
12 59
12 2
12 87
12 22
13 2
14 75
14 9
14 90
15 74
16 76
17 74
17 5
18 17
18 95
18 89
18 26
19 99
19 6
20 79
20 81
21 43
21 45
21 74
22 93
22 77
22 39
22 21
23 26
23 74
23 15
23 22
24 30
24 55
25 19
25 32
25 83
26 79
26 38
27 67
27 8
28 20
29 53
30 55
30 92
31 87
31 65
32 57
33 13
33 37
33 53
34 91
34 33
35 13
36 27
36 13
36 29
37 83
38 12
39 41
40 23
40 66
40 11
40 27
41 9
41 8
41 69
41 19
42 67
42 7
42 54
43 98
43 48
43 16
43 63
44 45
44 14
45 21
45 85
46 44
47 84
47 97
47 63
48 53
48 10
49 39
49 43
50 49
50 39
50 48
50 86
51 34
52 97
52 9
52 8
52 64
53 58
53 11
53 84
53 41
54 5
55 30
55 69
56 9
57 33
範例輸出4:
2

Answer 1

from collections import deque
import linecache as lc

def judgeP(ress, parent):
    result = []
    for idx, ii in enumerate(ress):
        if ii[-1] == parent:
            result.append((idx, ii))
    return result

def BFS(friends, one, two, three):
    q = deque()
    q.append(one)
    s = set()
    s.add(one)
    res = [[one]]
    while len(q) > 0:
        friend = q.popleft()
        listtmp = judgeP(res, friend)
        ff =friends.get(friend, [])
        for i in ff:
            for j in listtmp:
                if j[0] != -1:
                    res.append(j[1] + [i])
            if i not in s:
                q.append(i)
                s.add(i)

    result = []
    for i in res:
        if i[0] == one and i[-1] == three and two in i:
            result.append(i)
    return result


d = {}
ii = 1
while True:
    line = lc.getline("test.txt", ii)  #用文件代替输入
    if line == "":
        break
    line = line.replace("\n", '')
    if ii == 1:
        N, X, Y, Z = map(int, line.split())
    else:
        x, y = map(int, line.split())
        d[x] = d.get(x, []) + [y]
    ii += 1
    
result = BFS(d, X, Y, Z)
if result:
    a1 =len(sorted(result, key = lambda x: len(x))[0])
    res = [i for i in result if len(i) == a1]
    for i in res:
        print(a1 - 1)
        print('--'.join(map(str, i)))
else:
    print("No Way")