N—E—E 2022-02-05 10:14 采纳率: 59.5%

# pta哈利波特的考试(数据结构7-8)后两个测试集为什么过不了？

6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80

###### 问题相关代码，请勿粘贴截图
``````infinity = float('inf')

class mgragh:
def __init__(self,n,m) -> None:
self.mgragh = [[infinity for i in range(n+1)] for j in range(n+1)]
self.edgenum = m
self.vernum = n

# 读取邻接矩阵
for i in range(self.edgenum):
v1, v2, weight = map(int, input().split())
self.mgragh[v1][v2] = weight
self.mgragh[v2][v1] = weight

# floyd算法
def floyd(self)->list[list[int]]:
# 初始化dist矩阵
dist = [[infinity for i in range(self.vernum+1)] for j in range(self.vernum+1)]
for i in range(1,self.vernum+1):
for j in range(1,self.vernum+1):
if self.mgragh[i][j] < infinity:
dist[i][j] = self.mgragh[i][j]
# floyd
for i in range(1,self.vernum+1):
for j in range(1,self.vernum+1):
for k in range(1,self.vernum+1):
if dist[i][k]+dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist

# 求最长距离的最小值
def judge(self,D:list[list[int]]):
ans:int = 0
max_dist = 0
final_dist = infinity
for subans in range(1,self.vernum+1):
max_dist = 0
for j in range(1,self.vernum+1):
if j == subans:
continue
#if D[subans][j] == infinity:
#    break
if D[subans][j] > max_dist: max_dist=D[subans][j]
if max_dist != infinity:
if max_dist < final_dist:
ans = subans
final_dist = max_dist
if ans == 0: print(ans)
else: print("{} {}".format(ans,final_dist))

if __name__ == '__main__':
n,m = map(int, input().split())
g = mgragh(n,m)
dist = g.floyd()
#print(dist)
g.judge(dist)

``````

• 写回答

• 系统已结题 2月15日
• 已采纳回答 2月7日
• 创建了问题 2月5日

#### 悬赏问题

• ¥15 如何修改为正确的？求解决
• ¥15 django访问管理员界面问题
• ¥20 python homework完成
• ¥20 求解 多变量系统的最小二乘辨识问题的推导以及matlab仿真