求改題程式碼
小白要到納美克星的城市旅遊，某些城市之間有傳輸通道可以走。小白聽說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
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")
兄弟你的这个是数据结构里面的图啊，或者你可以用贪心算法来比较
深度优先搜索或广度优先搜索
直接思维就是遍历每一条路径是否通。你是台湾的同胞吗？