问题遇到的现象和发生背景
题目:
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
# 读取邻接矩阵
def readmat(self)->None:
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)
g.readmat()
dist = g.floyd()
#print(dist)
g.judge(dist)