求改題程式碼
小白要到納美克星的城市旅遊,某些城市之間有傳輸通道可以走。小白聽說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
Python-程式代碼問題
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
4条回答 默认 最新
- chuifengde 2022-01-05 14:37关注
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")
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报 编辑记录
悬赏问题
- ¥15 关于#matlab#的问题:在模糊控制器中选出线路信息,在simulink中根据线路信息生成速度时间目标曲线(初速度为20m/s,15秒后减为0的速度时间图像)我想问线路信息是什么
- ¥15 banner广告展示设置多少时间不怎么会消耗用户价值
- ¥16 mybatis的代理对象无法通过@Autowired装填
- ¥15 可见光定位matlab仿真
- ¥15 arduino 四自由度机械臂
- ¥15 wordpress 产品图片 GIF 没法显示
- ¥15 求三国群英传pl国战时间的修改方法
- ¥15 matlab代码代写,需写出详细代码,代价私
- ¥15 ROS系统搭建请教(跨境电商用途)
- ¥15 AIC3204的示例代码有吗,想用AIC3204测量血氧,找不到相关的代码。