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

    # 读取邻接矩阵
    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)
            

运行结果及报错内容

代码有两个问题，第一个就是Floyd中k，k代表的意义你没有理解，应该放在最外层循环。第二个就是你取最大值的时候初始化的也设置inf，遍历的时候也应该记录一下下标，只需要维护最大值和下标就行了，下面的第二个if循环显得没必要

本题可考虑使用Floyd算法求解
找Floyd矩阵后的每行的最大（每个点到其他点消耗魔咒的最大），从这个最大中找一个最小。
然后来说一下错误：
第一处错误：最大N的等边长环,解不唯一,输出最小编号。解不唯一，需要找出最优解(题目需求的 此处是最小的)，输出最小的。
第二处错误：最大N,最大M,随机完全图。最大N和M，图是随机完全图。

以上仅供参考，
希望对题主有所帮助！

采用动态规划思想，表示和之间可以通过编号为的节点的最短路径。初值为原图的邻接矩阵。则可以从转移来，表示到不经过这个节点。也可以从转移过来，表示经过这个点。意思即然后你就会发现最外层一维空间可以省略，因为只与有关。虽然这个算法非常简单，但也需要找点时间理解这个算法，就不会再有这种问题啦。
Floyd算法的动态规划的解释，我这里再做一点补充。为 i, j之间的最短路只使用 作为中间节点的最短路，那么根据动态规划方程，可以知道:。那么这个朴素的算法是应该使用空间的。因为动态规划的k只使用了和k - 1相关的信息，那么最简单的方式就是我们只使用2个的矩阵来存储最后两个k - 1, k的结果。经典的代码中为什么能成立，是因为如下原因，当迭代到k的时候，节点的更新可能存在如下四种情况之一:正确的动态规划应该采用第一种形式，而2，3，4中情况都会有可能在中间节点应用了个节点。但是k不可能是或者的中间节点，否则在最短路上就存在环了,而floyd要求图不存在负环，如果最短路上存在环，那么完全可以把环去掉得到一个更短的路径（矛盾）。所以证明k不可能是或者的中间节点，也就能得出:所以在迭代的时候完全可以在一个二维矩阵上迭代。

直接给你发代码，希望你能点击采纳

    for(k=1;k<=N;k++)
      for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
          if(k==i||k==j||i==j)
            continue;
          if(length[i][j]>length[i][k]+length[k][j])
            length[i][j]=length[j][i]=length[i][k]+length[k][j];
        }   //含义 i j之间是否可以通过 k来缩短距离
      }
#include<stdio.h>

#define INF 10000

struct animal{
int index;
int maxLength;
};

int main(void)
{
    int N,M;
    int i,j,k;
    fscanf(stdin,"%d %d",&N,&M);   //N是动物数目 M是魔咒条数
    int length[N+1][N+1];    //邻接矩阵存储 动物从1开始编号
    struct animal target;      //目标动物
    target.index=-1;           //先初始化为-1
    target.maxLength=INF;      //初始化无穷

    for(i=0;i<=N;i++)
      for(j=0;j<=N;j++)
        if(i==j)
          length[i][j]=0;      //到自己的距离为0
        else
          length[i][j]=INF;    //INF代表不可到达

    for(i=0;i<M;i++){
      int m,n,l;            //分别为两个动物编号以及距离
      fscanf(stdin,"%d %d %d",&m,&n,&l);
      length[m][n]=l;
      length[n][m]=l;         //为无向图
    }

    for(k=1;k<=N;k++)
      for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
          if(k==i||k==j||i==j)
            continue;
          if(length[i][j]>length[i][k]+length[k][j])
            length[i][j]=length[j][i]=length[i][k]+length[k][j];
        }   //含义 i j之间是否可以通过 k来缩短距离
      }

    for(i=1;i<=N;i++){
      int max=-1;
      for(j=1;j<=N;j++){
        if(length[i][j]>max)
          max=length[i][j];
      }
      if(max<target.maxLength){
        target.maxLength=max;
        target.index=i;
      }
    }

    if(target.index==-1)
      printf("0");
    else
      printf("%d %d",target.index,target.maxLength);

    return 0;
}