加载中
题目描述 复制
暑假来临，小明从A城市岀发去H城市旅游，中间需要经过若干个城市。如图a所示，带箭头的边表示行驶的方向，上面的数字表示两个城市间的距离。小明从A城市到H城市的驾车路线可以选择“A->D->G->H” ,也可以选择“A->E->F->H” ,还可以选择“A->B->C->H”等，其中“A->E->F->H”为所有路线中的最短路线方案，路线总长度为30(12+3+5+10)。编写程序实现根据从A城市到H城市的路线图，求小明从A城市到H城市的最短驾车长度，程序运行效果如图c所示。
提示：A城市到H城市的路线图存储在文本文件“ map. txt ”中，文件存储数据格式如图b所示，城市A、B、C、D、E、F、G、H分别编号为0〜7。
提示：A城市到H城市的路线图存储在文本文件“ map. txt ”中，文件存储数据格式如图b所示，城市A、B、C、D、E、F、G、H分别编号为0〜7。
输入
0 3 12
0 4 16
0 1 10
1 2 7
2 7 25
3 6 8
3 5 9
3 4 3
4 5 5
4 2 9
5 7 10
6 7 15
0 4 16
0 1 10
1 2 7
2 7 25
3 6 8
3 5 9
3 4 3
4 5 5
4 2 9
5 7 10
6 7 15
输出
A->D->E->F->H
30
30
样例输入 复制
0 3 12
0 4 16
0 1 10
1 2 7
2 7 25
3 6 8
3 5 9
3 4 3
4 5 5
4 2 9
5 7 10
6 7 15
样例输出 复制
A->D->E->F->H
30
代码填空 复制
import sys
n=8 #共有8个城市
dcity={0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F",6:"G", 7: "H"}
a=[[0 for i in range(n)]for j in range(n)]
for line in sys.stdin:
s=line.strip()
b=list(map(int, s.split()))
a[b[0]][b[1]]=b[2] #记录两个城市间的距离
q=[0]*200 #初始化队列
path=[0]*n #记录驾车方案
f=[False]*n
ans=[9999]*n
destination=7 #目的城市H的编号为7
head=tail=0
q[tail]=0
tail+=1
f[0]=True
ans[0]=0
while head<tail:
...
...
p=destination
s=""
while p!=0:
s=dcity[path[p]]+"->"+s
p=path[p]
s=s+dcity[destination]
print(s)
print(ans[destination])
必须/禁用关键字
禁用关键字:
exit
eval
exec