N—E—E
2022-02-05 10:14
采纳率: 61.1%
浏览 34
已结题

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

问题遇到的现象和发生背景

题目:

img

img


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)
            





运行结果及报错内容

img

4条回答 默认 最新

相关推荐 更多相似问题